Formal language theory/Generators and acceptors

Finite Automata edit

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.