NTIN071 Automata and grammars: tutorial (Spring 2024)

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

Office hours (in S303):

• Monday 12:20
• Wednesday 14:00
• Thursday 15:40

or individually by appointment. (If you plan to come but expect to be late, please email me.)

Credit requirements

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

Program

1st class (Feb 22)

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

2nd class (Feb 29)

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

3rd class (Mar 7)

• Program: Equivalent and minimal representations, testing properties, nondeterminism, closure under operations
• Worksheet: tutorial3.pdf

4th class (Mar 14)

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

5th class (Mar 21)

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

6th class (Mar 28)

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

7th class (Apr 4)

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

8th class (Apr 11)

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

9th class (Apr 18)

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

10th class (Apr 25)

• Program: Pushdown automata.
• Worksheet: tutorial10.pdf

11th class (May 2)

• Program: Turing machines
• Worksheet: tutorial11.pdf

12th class (May 9)

• Program: Homework due date! More about TMs, Leftovers.
• Worksheet: tutorial12.pdf

13th class (May 16)

• Program: The test!

14th class (May 23)

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

Useful links

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