Section outline

  • October 4th, Wednesday (12:30-14:30)

    Introduction to the theory of automata

    • Notion of language
    • Extensional and intensional specification of a language
    • Set-formers
    • Languages and decision problems (to be revisited later)

    Finite state automata

    • Deterministic finite state automata (DFA)
    • String processing
    • Mathematical definition of DFA
    • Graphical representations for DFA
    • Extended transition function
    • Example

    References

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