Section outline

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

    Finite state automata

    • Conversion of an \(\varepsilon\)-NFA into a DFA: subset construction and \(\varepsilon\)-closure
    • Theorem (proof omitted): Equivalence between \(\varepsilon\)-NFA and DFA

    Regular expressions

    • Set operators over languages
    • Inductive definition of regular expression and of the generated language
    • Examples
    • Operator precedence
    • Tree structure underlying a regular expression
    • Exercises

    References

    • Hopcroft et al., chapter 3