Three finite-automaton simulators written in C++ that show how the same idea grows in power and in complexity: a deterministic machine, a nondeterministic one, and a nondeterministic one with ε-moves. Each program prints the state path for the words it processes, and each comes with a transition diagram drawn from its Graphviz source.

All three work over the alphabet {0, 1} and print their transition table at the end of the run.

A four-state machine over the binary alphabet. It starts and accepts in state A, so it recognises words with an even number of 0s and an even number of 1s. The program walks the first 500 binary words and prints the state path of every accepted word.

• Exactly one transition per state and symbol.
• Invalid symbols are reported and stop the run.
• Example accepted path for 1001: A→C→D→C→A.

Nine states with several possible moves per symbol. A recursive backtracking search explores every branch and prints each path with its verdict; the word is accepted if at least one path ends in state 9. In the diagram, blue edges are symbol 0 and orange edges are symbol 1.

• Non-short-circuit | makes every branch run, so the full search tree is printed.
• Accepting condition: input consumed while standing in state 9.

Six states plus empty (ε) transitions that change state without consuming input. In the recursion this is a call that does not advance the input index. State E branches into B and C for free, and B can jump to the accepting state D at the end of the word.

• Dashed orange edges in the diagram are ε-transitions.
• Tested words: 1, 0, 000, 111, 011 accepted; 11, 01, 010 rejected.