Open Educational Resource
Baldwin, Doug; Jasinski, James; Klein, Matt; McAlevey, Jack; Parks, Ian; Rohe, Susanna; Wakwella, Praveen; Wilson, John; and Wojick, Kevin, "Nondeterministic Finite Automata Correspond to Deterministic Ones" (2018). Computability OER. 1.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
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.