Nondeterministic Finite Automata Correspond to Deterministic Ones

Authors

Doug Baldwin, SUNY GeneseoFollow
James Jasinski, SUNY Geneseo
Matt Klein, SUNY Geneseo
Jack McAlevey, SUNY Geneseo
Ian Parks, SUNY Geneseo
Susanna Rohe, SUNY Geneseo
Praveen Wakwella, SUNY Geneseo
John Wilson, SUNY Geneseo
Kevin Wojick, SUNY Geneseo

Document Type

Open Educational Resource (OER)

Publication Date

11-2018

Comments

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.

Recommended Citation

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.
https://knightscholar.geneseo.edu/computability-oer/1

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 License.