Section outline

  • October 6th, Friday (12:30-14:30)

    Finite state automata

    • Example (continued)
    • Language recognized by a DFA
    • The class of regular languages
    • Exercise
    • Nondeterministic finite state automata (NFA): basic idea
    • Interpretation by "independent" computations and interpretation by "oracle"
    • Example of NFA
    • Mathematical definition of NFA
    • Extended transition function for NFA

    References

    • Hopcroft et al., chapter 2