View article

We introduce the notion of a regular language, and show that regular languages are precisely those that are accepted by deterministic finite automata. We introduce nondeterminism, and prove that for automata, nondeterministic and deterministic machines have the same power, the trade-off being an exponential increase in the number of states. We finish with the Myhill-Nerode Theorem which shows how finite state is that same as having finite index for a certain canonical equivalence relation.