Section outline

  • October 10rd, Tuesday (12:30-14:30)

    Finite state automata

    • Language accepted by a NFA
    • Examples
    • Construction: Conversion of a NFA into a DFA through the subset construction

    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