Hide menu

TDDD14/TDDD85 Formal Languages and Automata Theory

Questions: contact Victor for lectures 1,2,3,4,5,6,14,15 and Jonas 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. Complementary video.
#8 CFG normal forms. (Ch. 2.1 in Sipser, Ch. 21 in Kozen). Lecture notes. Complementary video.
#9 Pushdown automata (PDA). (Ch. 2.2 in Sipser, Ch. 23, supplementary lecture E in Kozen). Lecture notes. Complementary video.
#10 Equivalence between CFG and PDA. (Ch. 2.2 in Sipser, Ch. 24, 25, supplementary lecture F in Kozen). Lecture notes. 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. 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. Complementary videos: LL(1) parsing and LR(0).
#13 LR(1) parsing. (Ch. 2.4 in Sipser). Lecture notes. 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.

Join the course room in Microsoft teams during the scheduled lecture time. Note that this is mainly an opportunity to ask for clarification if anything is unclear in the posted content. Follow the instructions specified in each subchannel: use the general channel to ask questions of general interest (these will be visible to all course participants), and use the help channel to inform the teacher that you need private help. For this to work you need to create a subchannel, and include the name of your subchannel in your help message (e.g., @teachers group X needs help with Y). This works best if you then have a video meeting already running in your subchannel.

Material from previous year

  • Slides for Christer's lectures
  • Slides for Jonas' lectures (Note that some slides are only accessible on campus for copyright reasons).
  • Additional material:
    • Text on LR(0) and LR(1). .
    • Example applications of (generalized) context-free grammars – definitions of syntax of programming languages. (More precisely, a context-free superset of the language is defined.)

    Page responsible: Victor Lagerkvist
    Last updated: 2021-03-19