Section outline

  • October 2nd, Thursday (14:30-16:30)

    Introduction to the theory of automata

    • Notion of language (continued)
    • Extensional and intensional specification of a language
    • Set-formers

    Finite state automata

    • Deterministic finite state automata (DFA)
    • String processing
    • Mathematical definition of DFA
    • Graphical representations for DFA
    • Extended transition function
    • Example: \( L = \{ w \; | \; w \in \{ 0, 1 \}^*, \#_0(w) \mbox{ is even}, \#_1(w) \mbox{ is even} \} \)

    References

    • Hopcroft et al., chapter 1
    • Hopcroft et al., chapter 2