Section outline

  • October 3rd, Friday (10:30-12:30)

    Finite state automata

    • Example (continued): \( L = \{ w \; | \; w \in \{ 0, 1 \}^*, \#_0(w) \mbox{ is even}, \#_1(w) \mbox{ is even} \} \)
    • 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
    • Examples

    References

    • Hopcroft et al., chapter 2