TDDD14 Formal Languages and Automata Theory

Timetable

For the course schedule search here.

Organization

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

Tutorials:

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
   LR-grammars
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: Ulf Nilsson
Last updated: 2011-08-25