Automata and Formal Languages: Examples

Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.

Large Example

This example illustrates a number of operations on NFAs and DFAs.

It starts with a DFA accepting the language with an even number of a's and an even number of b's.
This is transformed into a regular expression.
The regular expression is transformed into an epsilon-NFA.
Epsilon transitions are removed.
The result is determinized.
The resulting DFA is minimized (states accepting the same language are drawn in the same color) yielding the original DFA.