Section outline

  • October 4th, Friday (08:30-10: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
    • Language accepted by a NFA

    References

    • Hopcroft et al., chapter 2