NTIN071 Automata and Grammars (Spring 2025)

This is the webpage of the English lecture (Monday, 12:20pm in S3) taught by Jakub Bulín.:

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

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

Information about exams, including a list of exam questions:

• about-exams.pdf

Tentative schedule

Lecture 1 (Feb 17)

• 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 24)

• 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 3)

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

Lecture 4 (Mar 10)

• 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 17)

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

Lecture 6 (Mar 24)

• 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 31)

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

• 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 14)

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

Lecture 10 (Apr 28)

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

Lecture 11 (May 5)

• 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 12)

• 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 19)

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