Document Type

Open Educational Resource (OER)

Publication Date



An important and initially surprising result about finite automata is that every nondeterministic finite automaton is equivalent to a deterministic one, i.e., nondeterminism doesn't add any computational power to the basic model. Maheshwari and Smid give the construction that shows how to create a deterministic finite automaton from a nondeterministic one, but don't include a proof that this construction is correct. This resource provides that correctness proof.

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License. (31 kB)