# 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 $Q$  of states, a finite alphabet $\Sigma$  of input (or output) symbols, a state transition function $\delta :Q\times \Sigma \rightarrow Q$ , an initial state $q_{0}\in Q$  and a set of final states $Q_{F}\in Q$ .

The transition function is extended to words by $\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? $(\{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.