NFAs and Complements
Explore the concept of complementing regular languages by understanding why NFAs cannot be used directly for complements, and how DFAs with inverted acceptance states correctly recognize complements. Learn the importance of state transitions and the role of missing moves when finding complements in finite automata.
We'll cover the following...
Finding the complement of a regular language using NFA
The complement of a regular language can be recognized by a machine obtained by inverting the acceptability of each state in a DFA that recognizes the language. The same strategy does not apply, however, to finding the complement of a regular language using a NFA. Why not?
One reason is that NFAs often omit possible moves for input strings, since they represent only what is acceptable in the language. When complementing a language, we are interested in what is not acceptable in the original language, so starting with a NFA won’t work.
Let’s consider the language , which the following NFA accepts.
Were ...