Hide menu

TDDD14/TDDD85 Formal Languages and Automata Theory


Course schedule from TimeEdit.


The difference between the courses will show up in the details of the contents of lecture 6, 11, and 15, and correseponding tutorials.

Lectures, planned content:
  1. Overview and introduction
  2. Deterministic finite automata
  3. Nondeterministic finite automata
  4. Finite automata with epsilon-transitions
    Regular expressions
  5. Myhill-Nerode theorem, minimization of finite automata
  6. Properties of regular languages
  7. Context-free grammars
  8. Simplification of context-free grammars, normal forms
  9. Pushdown-automata
  10. Context-free grammars and pushdown-automata
  11. Properties of context-free languages
  12. LL(1)-grammars (if there is time); LR(0)-grammars
  13. LR(1)-grammars
  14. Turing machines
  15. Undecidability
  16. The Chomsky hierarchy; summary of the course


  1. Basic concepts
  2. Finite automata
  3. Regular expressions and minimization of finite automata
  4. Properties of regular languages
  5. Context-free grammars
  6. Discussion/feedback on the first set of assignments
    Pushdown automata
  7. Properties of context-free languages
  8. Turing machines
  9. Discussion/feedback on the second set of assignments
Tutorials are basically problem solving sessions. This schedule may be modified according to needs.

Page responsible: Jonas Wallgren
Last updated: 2014-03-20