Section outline

  • October 15th, 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
    • Conversion of an \(\varepsilon\)-NFA into a DFA: subset construction and \(\varepsilon\)-closure
    • Theorem (proof omitted): Equivalence between \(\varepsilon\)-NFA and DFA

    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