Nondeterministic Finite Automata
Ganesh Lalitha Gopalakrishnan · 2019
This chapter introduces the key concept of nondeterminism through nondeterministic finite automata (NFA). NFA can be exponentially more succinct than deterministic finite-state automata (DFA). One can also view NFA as modeling parallel search in which each forked behavior pursues one search option. The chapter formally defines NFA and presents how the language of an NFA can be intuitively understood. Subset construction, the centrally important algorithm to convert an NFA to a DFA is explained. The chapter provides a complete illustration of a clever DFA minimization algorithm due to Brzozowski, to simply reverse the given DFA, determinize it, then reverse it, and determinize it again. The fact that subset construction yields a language-equivalent DFA ofcourse merits a proof. This can be argued at a high level by tracing the accepting paths in the DFA generated out of an NFA and relating it to corresponding paths in the NFA.