NTIN071 Automata and grammars: tutorial (Spring 2026)

This page contains information about my English tutorial class (Thu 12:20am in S11). If you are enrolled in Dr. Kuboň’s class, refer to him for information about your class.

Office hours during the teaching period (in S303):

• Monday 10:40am
• Thursday 2pm

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.

Getting the credit

The credit requirements are described in the PDF below, please review them, and aks any questions in class.

• credit-requirements.pdf
• sample-test.pdf
• written test date: Thursday, May 14 in class
• retake test dates: TBD

Tentative schedule (to be updated)

1st class (Feb 19)

• Program: Deterministic finite automaton, recognized language, regular languages
• Worksheet: tutorial1.pdf

2nd class (Feb 26)

• Program: Pumping Lemma , Myhill-Nerode theorem, Equivalent and minimal representations
• Worksheet: tutorial2.pdf

3rd class (Mar 5)

• Program: Testing properties, nondeterminism, subset construction, closure under set operations
• Worksheet: tutorial3.pdf

4th class (Mar 12)

• Program: Closure under string operations
• Worksheet: tutorial4.pdf

5th class (Mar 19)

• Program: Regular expressions, 2-way automata
• Worksheet: tutorial5.pdf

6th class (Mar 26)

• Program: Formal grammars, regular and context-free grammars
• Worksheet: tutorial6.pdf

7th class (Apr 2)

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

8th class (Apr 9)

• Program: Pushdown automata, conversion between PDA and CFG
• Worksheet: tutorial8.pdf

9th class (Apr 16)

• Program: Properties of context-free languages, DPDA
• Worksheet: tutorial9.pdf

10th class (Apr 23)

• Program: Turing Machines
• Worksheet: tutorial10.pdf

11th class (Apr 30)

• Program: Intro to complexity theory
• Worksheet: tutorial11.pdf

12th class (May 7)

• Program: More about complexity
• Worksheet: continue with tutorial11.pdf

Bonus 13th class (May 21)

• Program: Review & Exam preparation

Useful links

• The lecture
• 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” and “tutorial” 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 tutorials streamed or recorded? — No, but a plenty of office hours time is available for those who miss a class. Use it!