Jump to content

Formal language theory/Generators and acceptors

From Wikiversity

Finite Automata

[edit | edit source]

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.