NTIN071 Automata and Grammars (Spring 2024)

This is the webpage of the English lecture taught by Jakub Bulín.

• 🇬🇧 The lecture is accompanied by a tutorial. The website for my tutorial class is here. If you are enrolled in the tutorial class of Vladislav Kuboň, please direct all questions regarding the tutorial and the credit to him.
• 🇨🇿 Informace o českých cvičeních Jakuba Bulína najdete zde.
• 🇨🇿 Česká přednáška Marty Vomlelové sídlí zde.

Office hours (in S303):

• Monday 12:20
• Wednesday 14:00
• Thursday 15:40

or individually by appointment. (If you plan to come but expect to be late, please email me.)

Info about exams

The details will be specified later.

Tentative schedule

Lecture 1 (Feb 19)

• Program: Introduction, Deterministic Finite Automaton, Regular Languages, Pumping Lemma
• Slides: slides1.pdf

Lecture 2 (Feb 26)

• Program: Myhill–Nerode theorem, Equivalent and Minimal Representations
• Slides: slides2.pdf

Lecture 3 (Mar 4)

• Program: Nondeterminism, Closure properties
• Slides: slides3.pdf

Lecture 4 (Mar 11)

• Program: Regular expressions, Kleene’s theorem, String substitution
• Slides: slides4.pdf
• Addendum: 2way-and-output-automata.pdf

Lecture 5 (Mar 18)

• Program: Grammars, Regular and context-free grammars
• Slides: slides5.pdf

Lecture 6 (Mar 25)

• Program: Chomsky normal form, Pumping lemma for context-free languages
• Slides: slides6.pdf

Lecture 7 (Apr 8)

• Program: The CYK algorithm, Pushdown automata
• Slides: slides7.pdf

Lecture 8 (Apr 15)

• Program: Equivalence of PDA and CFG, Deterministic PDA
• Slides: slides8.pdf

Lecture 9 (Apr 22)

• Program: Closure properties of context-free languages, Dyck languages
• Slides: slides9.pdf

Lecture 10 (Apr 29)

• Program: Turing Machines, Linear-bounded automata
• Slides: slides10.pdf

Lecture 11 (May 6)

• Program: Intro to Computability theory, Universal TM, Diagonal language, Post’s theorem
• Slides: slides11.pdf

Lecture 12 (May 13)

• Program: Undecidable problems, Post’s correspondence problem
• Slides: slides12.pdf

Lecture 13 (May 20)

• Program: Intro to Complexity theory
• Slides: slides13.pdf

Resources and useful links

• Online copy of Hopcroft’s textbook “Introduction to Automata Theory, Languages, and Computation” (3rd edition); several physical copies are available in the library as well.
• Sipser’s textbook “Introduction to the theory of computation” (3rd edition), a physical copy is in the library
• NTIN071 in the SIS
• Turing Machine Simulator
• Finite State Machine designer

Frequently asked questions (FAQ)

• What should I do if I have a question? — Check the FAQ. If you don’t see the answer here email me putting “ntin071” in the subject.
• What if I want a consultation? — Talk to me after class, come to the scheduled office hours, or email me to arrange an appointment.
• Are the lectures streamed or recorded? — No, but a plenty of office hours time is available for those who miss a lecture. Use it!