Brad Fitzpatrick (brad) wrote,
Brad Fitzpatrick

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.


  • Ukraine

    Nobody reads my LiveJournal anymore, but thank you to everybody in Russia protesting Putin's insane war against Ukraine. (I know it's risky…

  • Happy Birthday!

    Happy 20th Birthday, LiveJournal! 🐐🎂🎉

  • hi

    Posting from the iPhone app. Maybe I'm unblocked now.

  • Post a new comment


    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.