An **alphabet** $\Sigma$ is a finite set of symbols. For example $\{0,1\}$ is an alphabet and $\{a,b,c,d\}$ is an alphabet. An **word** is a finite set of symbols from an alphabet $\Sigma$. One word for the alphabet $\{a,b,c,d\}$ would be $abc$ and another one would be $aaab$. The length of a word $w$ is defined as the number of symbols it has. So the length of the word $01010$ from the alphabet $\{0,1\}$ would be $5$. Every alphabet contains the **empty word**. The empty word is the word with size $0$. The set of all words that can be created from an alphabet is $\Sigma^* $.

Words can be combined. Combining word $w = 010$ and word $v = 101$ creates a new word $wv = 010101$. Combining any for with the empty word results in the same word: $w\varepsilon = w = \varepsilon w$.

$\Sigma^* $ is created with the *Kleene Star* algorithm. The Kleene Star algorithm creates every possible word for an alphabet $\Sigma$.

Given an alphabet $V$:

$$V_0 = \{\varepsilon\}$$ $$V_1 = V$$

now recursively define for all i > 0:

$$V_{i+1} = \{wv | w \in V_i, v \in V\}$$

Example: $V = \{ a, b \}$ then $V_0 = \{ \varepsilon \}$, $V_1 = \{ a, b \}$, $V_2 = \{ a, b, aa,ab,ba,bb \}$,…

A **Formal language** *L* over an alphabet $\Sigma$, is a subset of $\Sigma^*$.

Example: $\Sigma = \{a,b,c\}$. One viable language would be $L_1 = \{aa,ab,bb,bc,abc,cc\}$. $L_1$ has $6$ elements. Another language for the same alphabet could be $L_2 = \{a^n b^n c^n | n \in \mathbb{N}\}$. $L_1$ is defined by it’s elements. $L_2$ on the other hand is defined by how to build words that are in $L_2$. $L_2 = \{abc,aabbcc,aaabbbccc, \dots\}$.

DFA’s are used to determine if a word $w$ is element of an language $L$. A deterministic finite automaton is defined as ${\mathfrak {A}}=\left(Q,\,\Sigma ,\,\delta ,\,q_{0},\,F\right)$.

- $Q$ is the finite number of states of the DFA
- $\Sigma$ is an alphabet
- $\delta$ is a transition function $\delta :Q\times \Sigma \rightarrow Q$
- $q_0$ is the start state of the DFA $q_0 \in Q$
- $F$ is a set of final states $F \subseteq Q$

Example:

This DFA accepts binary numbers that are multiples of 3. $Q = \{S_0, S_1, S_2\}$, $\Sigma = \{0,1\}$,

$\delta =$

$0$ | $1$ | |
---|---|---|

$\rightarrow S_0^*$ |
$S_0$ | $S_1$ |

$S_1$ |
$S_2$ | $S_0$ |

$S_2$ |
$S_1$ | $S_2$ |

$q_0 = S_0$, $F = \{S_0\}$.

In the transfer table a state with $\rightarrow$ in front it means its a start state. The other symbol $^*$ means its a final state.

In a NFA there can be states where you can choose from different options to “move” through the NFA. This makes the NFA non-deterministic because the “path” is not set in stone. Every DFA is automatically a NFA but not every NFA is a DFA.

In this example you can choose to stay in $S_0$ when you read a $1$ or you can choose to move to $S_1$. This means the NFA only accepts words that end with a $1$.

The transfer table for the NFA:

0 | 1 | |
---|---|---|

$\rightarrow S_0$ | $S_0$ | $\{S_0, S_1\}$ |

$S_1^*$ | $\varnothing$ | $\varnothing$ |

Take the transfer table from the NFA and take the start state and look where it leads for each symbol and make a new set from them. If the set contains a final state also make the new state a final state. Repeat that for each new set until no set wasn’t handled.

If you want you can rename the sets afterwards.

Example with the NFA from above:

$0$ | $1$ | |
---|---|---|

$\rightarrow S_0$ | $S_0$ | $\{S_0, S_1\}$ |

$\{S_0, S_1\}^*$ | $S_0$ | $\{S_0, S_1\}$ |

The resulting DFA from the NFA: