Preliminaries of Automata Theory & Set Theory

Set Theory Recap

$\emptyset \{\emptyset\}$
- The empty set or a set containing the empty set.
$\{a_1,a_2,\ldots,a_n\}$
- This is a set.
$a\in A,B\subseteq A$
- $a$ in in $A$ and $B$ is a subset of $A$.
$A\cup B,A\cap B,A\backslash B$
- Sum, intersection and difference.
$2^A=\{B\vert B\subseteq A \}=\{B:B\subseteq A\}$
- Denotes all the subsets of a given set.
$(a_1,a_2,\ldots,a_n)$
- This is sequence, not a set, due to the round brackets.
- Order and repetition doesn’t matter in sets.

Problems which have binary answers are called decisions problems. We will be focusing on decision problems not other types of problem.

We can reduce a problem to a decision problem to make it easier to solve.

Consider the following boolean formula:

\[(x'\vee y' \vee z)\wedge(\neg x \vee y \vee \neg z)\]

We want to find which values of true $\top$ and false $\bot$ give an output of true.

We can use the following methods:

Strings are a list of characters from a finite set. They can also be called words. To define strings, we start with an alphabet.

An alphabet is a finite set of symbols.

You could have the following alphabets:

A string over alphabet $\Sigma$ is a finite sequence of symbols in $\Sigma$.

For example:

The empty string is denoted by $\varepsilon$

We write $\Sigma^*$ for the set of all strings over $\Sigma$.

We write $\Sigma^+$ for the set of all non-empty strings.

A language is a set of strings over the same alphabet. Languages define “yes/no” problems.

Consider the following example:

stop, to and toe are in $L_1$

$\varepsilon$, oyseter are on in $L_1$

Therefore:

\[L_1=\{x\in \Sigma^*_1 \vert x \text{ contains the substring } \mathtt{to}\}\]

Another language could be:

\[L_2=\{s\# s \vert s\in \{a,b,\ldots,z\}*\}\]

This is any number of letters then a hash then any number of letters: ajdj#kjd