Section outline

  • October 10th, Thursday (08:30-10:30)

    Finite state automata

    • Examples
    • Construction: Conversion of a NFA into a DFA through the subset method
    • Construction: Conversion of a NFA into a DFA through lazy evaluation
    • Theorem: correctness of the subset construction
    • Theorem: equivalence of DFA and NFA

    Exercises

    • Define DFAs for the following three languages:
      • \( L_1 = \{ w \; | \; w \in \{0,1\}^\ast,\) the pattern 011 occurs at least once within \( w \}\)
      • \( L_2 = \{ w \; | \; w \in \{0,1\}^\ast,\) the pattern 011 does not occur within \( w \}\)
      • \( L_3 = \{ w \; | \; w \in \{0,1\}^\ast,\) the pattern 011 occurs exactly once within \( w \}\)

    References

    • Hopcroft et al., chapter 2