Hide menu

TDDD14/TDDD85 Formal Languages and Automata Theory

Questions: contact Victor for lectures 1,2,3,4,5,6,14,15 and August for lectures 7,8,9,10,11,12,13,16.

Lecture material

#1 Introduction and formal languages (Ch. 0 in Sipser, Ch. 1 in Kozen).
Lecture notes. Videos.
#2 Deterministic finite automata (DFA) (Ch. 1.1 in Sipser, Ch. 3,4 in Kozen). Lecture notes. Videos.
#3 Nondeterministic finite automata (NFA) (Ch. 1.2 in Sipser, Ch. 5,6 in Kozen). Lecture notes. Videos. Additional third-party material: Complementary video. Common misconception.
#4 Closure properties and regular expressions (Ch. 1.3 in Sipser, Ch. 7,8,9 in Kozen). Lecture notes. Videos. Third party complementary videos: closure properties, definition of regular expressions, and simplification of regular expressions.
#5 DFA minimisation (Ex. 7.25 in Sipser, Ch. 13 in Kozen). Lecture notes. Videos.
#6 Pumping lemma, Myhill-Nerode, and homomorphisms (Ch. 1.4, Ex. 1.48, 1.60 in Sipser, Ch. 10,11,12,15,16 in Kozen). Lecture notes. Videos. Third party complementary video: pumping lemma .
#7 Context-free grammars (CFG). (Ch. 2.1 in Sipser, Ch. 19 in Kozen). Lecture notes. Slides. Complementary video.
#8 CFG normal forms. (Ch. 2.1 in Sipser, Ch. 21 in Kozen). Lecture notes. Slides. Complementary video.
#9 Pushdown automata (PDA). (Ch. 2.2 in Sipser, Ch. 23, supplementary lecture E in Kozen). Lecture notes. Slides. Complementary video.
#10 Equivalence between CFG and PDA. (Ch. 2.2 in Sipser, Ch. 24, 25, supplementary lecture F in Kozen). Lecture notes. Slides. Complementary video part 1 and part 2.
#11 Properties of context-free languages and the pumping lemma for context-free languages (Ch. 2.3 in Sipser, Ch. 22 in Kozen). Lecture notes. Slides. Complementary videos: closure properties and pumping lemma for context-free languages.
#12 LL(1) and LR(0) parsing. (Ch. 2.4 in Sipser, Ch. 26 in Kozen). Lecture notes. Slides. Complementary videos: LL(1) parsing and LR(0).
#13 LR(1) parsing. (Ch. 2.4 in Sipser). Lecture notes. Slides. Complementary video: LR(1) items.
#14 Turing machines. (Ch. 3 in Sipser, Ch. 28, 29 in Kozen). Lecture notes. Videos. Third party complementary videos: Turing machines and additional examples.
#15 Undecidability and reductions. (Ch. 4, 5.3 in Sipser, Ch. 31, 32, 33 in Kozen). Lecture notes. Videos. Third party complementary videos: decidability and non-Turing recognisable languages , the halting problem , and reductions.
#16 The Chomsky hierarchy, summary. Lecture notes.

Page responsible: Victor Lagerkvist
Last updated: 2024-05-08