NTIN071 Automata and Grammars (Spring 2026)

This is the webpage of the English lecture (Monday, 9am in S4) taught by Jakub Bulín.:

• 🇬🇧 The lecture is accompanied by a tutorial. The website for my tutorial class (Thursday, 12:20pm in S11) is here. If you are enrolled in the tutorial class of Vladislav Kuboň, (Tuesday, 10:40am in S11), 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):

• TBD

or individually by appointment.

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

Info about exams

Information about exams, including a list of exam questions:

• about-exams.pdf

Tentative schedule

Lecture 1 (Feb 16)

• Program: Introduction, Deterministic Finite Automaton, Regular Languages, Pumping Lemma
• Slides: slides1.pdf
• Supplemental resources: Hopcroft 1.1, 1.5, 2.1-2, 4.1; Sipser 1.1, 1.4

Lecture 2 (Feb 23)

• Program: Myhill–Nerode theorem, Equivalent and Minimal Representations
• Slides: slides2.pdf
• Supplemental resources: Hopcroft 4.4; for Myhill-Nerode theorem: Wikipedia, Stanford guide

Lecture 3 (Mar 2)

• Program: Nondeterminism, Closure properties
• Slides: slides3.pdf
• Supplemental resources: Hopcroft 2.3-5, 4.2-3; Sipser 1.2

Lecture 4 (Mar 9)

• Program: Regular expressions, Kleene’s theorem, String substitution
• Slides: slides4.pdf
• Addendum: 2way-and-output-automata.pdf
• Supplemental resources: Hopcroft 3.1-3.3; Sipser 1.3

Lecture 5 (Mar 16)

• Program: Grammars, Regular and context-free grammars
• Slides: slides5.pdf
• Supplemental resources: Hopcroft 5.1-5.4; Sipser 2.1

Lecture 6 (Mar 23)

• Program: Chomsky normal form, Pumping lemma for context-free languages
• Slides: slides6.pdf
• Supplemental resources: Hopcroft 7.1-2; Sipser 2.3

Lecture 7 (Mar 30)

• Program: The CYK algorithm, Pushdown automata
• Slides: slides7.pdf
• Supplemental resources: Hopcroft 7.4.4, 6.1-2; Sipser 2.1-2

Lecture 8 (Apr 13)

• Program: Equivalence of PDA and CFG, Deterministic PDA
• Slides: slides8.pdf
• Supplemental resources: Hopcroft 6.3-4, 7.4; Sipser 2.2

Lecture 9 (Apr 20)

• Program: Closure properties of context-free languages, Dyck languages
• Slides: slides9.pdf
• Supplemental resources: Hopcroft 7.3, for Dyck languages: Wikipedia

Lecture 10 (Apr 27)

• Program: Turing Machines
• Slides: slides10.pdf
• Supplemental resources: Hopcroft 8.2-5; Sipser 3.1-2

Lecture 11 (May 4)

• Program: TMs and Grammars, Linear-bounded automata and Context-sensitive grammars, Intro to Computability theory
• Slides: slides11.pdf
• Supplemental resources: Wikipedia articles Unrestricted grammar, Context-sensitive grammar; Hopcroft 8.1-2

Lecture 12 (May 11)

• Program: Universal TM, Diagonal language, Post’s theorem. Undecidable problems, Post’s correspondence problem
• Slides: slides12.pdf
• Supplemental resources: Hopcroft 8.1, 9.1-5; Sipser 4.1-2, 5.1-3

Lecture 13 (May 18)

• Program: Intro to Complexity theory
• Slides: slides13.pdf
• Supplemental resources: Hopcroft 10.1-4, 11.1-3; Sipser 7.1-5, 8.1-4

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!