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):

• Monday 10:40am
• Thursday 2pm

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 (preliminary version, may be slightly modified)

Tentative schedule (to be updated)

Lecture 1 (Feb 16)

• Program: Introduction, Deterministic Finite Automaton, Regular Languages, Myhill–Nerode theorem
• Slides: slides1.pdf
• Supplemental resources: Hopcroft 1.1, 1.5, 2.1-2; Sipser 1.1; for Myhill-Nerode theorem: Wikipedia, Stanford guide

Lecture 2 (Feb 23)

• Program: Pumping Lemma, Equivalent and Minimal Representations
• Slides: slides2.pdf
• Supplemental resources: Hopcroft 4.1, 4.4; Sipser 1.4

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, Two-way automata
• Slides: slides4.pdf with appendix
• 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, 7.4.3-4; Sipser 2.3

Lecture 7 (Mar 30)

• Program: Pushdown automata, Equivalence of PDA and CFG
• Slides: slides7.pdf
• Supplemental resources: Hopcroft 6.1-2; Sipser 2.1-2

Lecture 8 (Apr 13)

• Program: Deterministic PDA, Properties of CFLs
• Slides: slides8.pdf
• Supplemental resources: Hopcroft 6.3-4, 7.3-4; Sipser 2.2, for Dyck languages: Wikipedia

Lecture 9 (Apr 20)

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

Lecture 10 (Apr 27)

• Program: Intro to computability
• Slides: slides10.pdf

Lecture 11 (May 4)

• Program:
• Slides: slides11.pdf
• Supplemental resources: Wikipedia articles Unrestricted grammar, Context-sensitive grammar; Hopcroft 8.1-2

Lecture 12 (May 11)

• Program:
• Slides: slides12.pdf
• Supplemental resources: Hopcroft 8.1, 9.1-5; Sipser 4.1-2, 5.1-3

Lecture 13 (May 18)

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