Brad Fitzpatrick (brad) wrote,
Brad Fitzpatrick
brad

Stuff I don't care about:

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.

Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 8 comments