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

• TBA

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, closure under operations
• Worksheet: tutorial3.pdf

4th class (Mar 10)

• Program: Finish leftovers from the previous class
• Worksheet: Continue with tutorial3.pdf

5th class (Mar 17)

• Program: More on closure properties.
• Worksheet: the rest of the previous worksheet and Problem 1 in tutorial5.pdf

6th class (Mar 24)

• Program: Regular expressions
• Worksheet: problems 2-6 from tutorial5.pdf

7th class (Mar 31)

• Program: Formal grammars, regular and context-free grammars, bonus: 2-way automata
• Worksheet: tutorial7.pdf

8th class (Apr 7)

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

9th class (Apr 14)

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

10th class (Apr 28)

• Program: Pushdown automata
• Worksheet: tutorial10.pdf

11th class (May 5)

• Program: Homework due date!
• Program: Coversion between PDA and CFG
• Worksheet: Continue working on tutorial10.pdf, thentutorial11.pdf

12th class (May 12)

• Program: The test!

13th class (May 19)

• Program: Turing Machines, Intro to complexity theory
• Worksheet: Continue working on tutorial11.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!