Section outline

  • October 16th, Wednesday (10:30-12:30)

    Finite state automata

    • NFA with \(\varepsilon\)-transitions (\(\varepsilon\)-NFA): basic idea
    • Definition of \(\varepsilon\)-NFA
    • Definition of \(\varepsilon\)-closure
    • Extension of the transition function
    • Language accepted by an \(\varepsilon\)-NFA

    Exercise

    • Let \(\Sigma = \{a,b\}\) and let \(L = \{ w \; | \; w = xby, \; x,y \in \Sigma^\ast, \; |x| + |y| = 2n, \; n \geq 0 \}\). Show that \(L\) is a regular language (exercise 2, second question, final exam of 2024/02/22))

    References

    • Hopcroft et al., chapter 2