Section outline

  • October 3rd, Thursday (08:30-10:30)

    Introduction to the theory of automata

    • String concatenations and its properties
    • 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