Language and Automata

Formal languages exploit sets of words and are involved in many fields of computer science such as text processing, programming languages, theoretical computer science, or complexity theory. The course introduces the main classes of languages to which different models are associated (finite automata, grammars, Turing machines).

Teaching time performed: 12 hours of lectures, 9 hours of tutorials, and 3 hours of practical classes around abstract syntax trees in Python.

Part of the teaching team for the school year 2021-2022 and 2022-2023.

Instructors: Pascale Le Gall, Marc Aiguier, and Fabrice Popineau.

Student level: Third year (~M2/MSc).


  • Regular languages:
    • Regular expressions
    • Finite automata
    • Completion and minimisation of automata
    • Kleene’s theorem
  • Context-free language:
    • Context-free grammar
    • Derivation tree
    • Pushdown automata
  • Turing machine
    • Universal Turing machines
    • Undecidable problems
    • Complexity classes
  • Application to lexical and syntactic analysis