worksheet3.org

In-Class Worksheet 3: Equivalence of NFAs and DFAs

NFAs to DFAs

Write an NFA for the following language and then convert it into a DFA: {w | w is an even number of 0s or an odd number of 1s} (or not and or xor)

Constructions and NFAs

Consider the following languages

• L_1 = { w | w has less than 3 0s}
• L_2 = { w | w has the substring 0101}

Now:

• write down NFAs for each of these
• combine them to make NFAs for the following languages
  • $L_1 ⋅ L_2$
  • $L_1 ∪ L_2$
  • $L_1^*$
  • $L_2^*$