# Formal language theory/Generators and acceptors

## Finite AutomataEdit

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 of states, a finite alphabet of input (or output) symbols, a state transition function , an initial state and a set of final states .

The transition function is extended to words by ,

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?

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.