NTIN071 Automata and Grammars (Spring 2025)

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 during the teaching period (in S303):

• TBA

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

Office hours during the exam period are scheduled ad hoc as needed. Email me your time constraints sufficiently in advance.

Info about exams

Will be specified later. <!– Information about exams, including a list of exam questions:

• about-exams-2024.pdf –>

Tentative schedule

Lecture 1 (Feb 17)

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

Lecture 2 (Feb 24)

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

Lecture 3 (Mar 3)

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

Lecture 4 (Mar 10)

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

Lecture 5 (Mar 17)

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

Lecture 6 (Mar 24)

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

Lecture 7 (Mar 31)

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

Lecture 8 (Apr 7)

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

Lecture 9 (Apr 14)

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

Lecture 10 (Apr 28)

• Program: Turing Machines
• Slides: slides10.pdf

Lecture 11 (May 5)

• Program: TMs and Grammars, Linear-bounded automata and CFG, Intro to Computability theory
• Slides: slides11.pdf

Lecture 12 (May 12)

• Program: Universal TM, Diagonal language, Post’s theorem. Undecidable problems, Post’s correspondence problem
• Slides: slides12.pdf

Lecture 13 (May 19)

• 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!