NTIN071 Automata and grammars: tutorial (Spring 2025)

This page contains information about my English tutorial class (Monday 3:40pm in S11). If you are enrolled in Dr. Kuboň’s class (Tuesday 2pm in S11), refer to him for information about your class.

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.

Credit requirements

• Detailed requirements to obtain the credit are described here.
• Homework assignment: due on May 5 at the beginning of class, homework.pdf
• Test: the date is May 12, list-of-requirements.pdf, sample-test.pdf

Program (will be updated)

1st class (Feb 17)

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

2nd class (Feb 24)

• Program: Pumping Lemma, Myhill-Nerode theorem
• Worksheet: tutorial2.pdf

3rd class (Mar 3)

• Program: Equivalent and minimal representations, testing properties, nondeterminism, subset construction
• Worksheet: tutorial3.pdf

4th class (Mar 10)

• Program: Closure properties of regular languages
• Worksheet: tutorial4.pdf

5th class (Mar 17)

• Program: Regular expressions (bonus: 2-way automata)
• Worksheet: tutorial5.pdf

6th class (Mar 24)

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

7th class (Mar 31)

• Program: Chomsky normal form, The CYK algorithm
• Worksheet: tutorial7.pdf

8th class (Apr 7)

• Program: Pumping lemma for context-free languages
• Worksheet: tutorial8.pdf

9th class (Apr 14)

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

10th class (Apr 28)

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

11th class (May 5)

• Homework due date!
• Program: Turing Machines
• Worksheet: tutorial11.pdf

12th class (May 12)

• The test!

13th class (May 19)

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

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!