Problem 1: 2.3.1 (83)
Imagine you have an NFA N(L), and then you do the subset construction to find the equivalent DFA D(L). Now, the final states of D(L) are any states which in their set contain at least one final state of N(L). If you then invert the states, the final states are any node which does not contain a final state of N(L), and this exactly what we want. However, let's see what happens if we try the naive way to invert the NFA N(L) by flipping all the states. Let's call this inverted NFA ~N(L). The final states of ~N(L) are now the old non-final states. Now, if we go to take the subset construction of ~N(L), the final states of ~D(L) are any node which contain at least one non-final state. However, there's nothing saying that the final states of ~D(L) can't also contain final states. Thus, inverting the states of an NFA do not create the complement, else the equivalent DFA of the inverted NFA would have its final nodes all consisting of sets that were previously entirely non-final.

• Post a new comment

#### Error

default userpic