Section outline

  • October 13th, Friday (12:30-14: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
    • Proof by mutual induction (Chapter 1, Section 1.4.4; Chapter 2, Exercise 2.9)

    Research & application highlights

    • Extensions of finite automata
    • Applications

    References

    • Hopcroft et al., chapter 2