# Formal language theory/Generators and acceptors

## Finite Automata

In this part, we will study the languages belonging to certain automata. One of the simplest kinds of automaton is the deterministic finite automaton (DFA). It consists of a finite set ${\displaystyle Q}$  of states, a finite alphabet ${\displaystyle \Sigma }$  of input (or output) symbols, a state transition function ${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$ , an initial state ${\displaystyle q_{0}\in Q}$  and a set of final states ${\displaystyle Q_{F}\in Q}$ .

The transition function is extended to words by ${\displaystyle \delta (q,\lambda )=q}$ ,

One can imagine that the automaton reads words and changes states accordingly (and can be driven into an undefined state, if no transition exists -- this state can just as well be represented as a non-accepting state with no way back, making the automaton complete), or that it outputs states.

Exercise: is this a deterministic finite automaton? Why or why not? ${\displaystyle (\{q_{0},q_{1}\},\{a,b\},\{(q_{0},a,q_{1}),(q_{1},a,q_{1}),q_{0},\{q_{1}\}\})}$

Exercise: Find a construction for transforming an NFA into an equivalent DFA and prove its correctness. Hint: what do you know after a letter has been read?

The key fact about finite automata is that such a machine can remember only a finite amount of information as it moves along the input. From this follow some syntactic properties of languages recognised by them.