Skip to content

Latest commit

 

History

History
151 lines (145 loc) · 4.69 KB

worksheet2Sol.org

File metadata and controls

151 lines (145 loc) · 4.69 KB
Raw

In-Class Worksheet: NFAs and Basic Constructions

NFAs

Try to write NFAs for the following languages

  • { w | w has at least three 1s }
  • { w | w is matched by the regular expression 10^*(1|0)}

Unions and Intersections

Write DFAs for the following two languages, then take both the union and intersection. When you’re done, do the same thing with them as NFAs and take the union of the NFAs.

  • {w | w starts with 3 0s} DFA:

    NFA:

  • {w | w ends with 3 1s} DFA:

    NFA:

Now to take the union for NFAs we just do a very simple connection between the two via ε transtions

Now the DFA case is way more annoying and has a total of 20 states: we’re going to write down a slightly simplified version that consists only of the states that are actually reachable in the system. We’re going to label all the states as qxy where x is the state of the DFA for the first language and y is the state of the DFA for the second language