Automata Theory and Formal Languages

Room: 24.21.03.86, Tuesdays 12:30-16:00

Tentative course schedule

9 October -- Introduction, Mathematical preliminaries. HW1: exercises 0.1 -- 0.13 (from 0.1, 0.2, 0.3, 0.6 select any two letters)
16 October -- Finite automata, Deterministic automata. HW2: exercises 1.3, 1.4 (e, g), 1.5d, 1.6 (g, h)
23 October -- NDFA, Regular languages, closure properties. HW3: 1.7c, 1.8b, 1.9b, 1.10b, 1.14, 1.15, 1.16, 1.19a, 1.20 b,c
30 November -- Pumping lemma for RL, minimization. HW4: 1.24, 1.28 b, 1.29 b (try to solve 1.29 a and 1.29 c on your own, then you can look into the solutions), 1.30, 1.31, 1.46a, 1.48
6 November -- Context-free languages, Chomsky normal form, Pushdown automata. HW 5 due 20 Nov: 1.46 c,d; 1.49; 1.54; 2.4 c, e; 2.6 b; 2.15; 2.26
13 November -- No class!
20 November -- Pumping lemma for PDA/context-free languages. HW6: 2.15, 2.16, 2.26, 2.30 (a, b)
27 November -- Church-Turing thesis, Turing Machines. HW7: 2.31, 2.36, provide a formal definition or a state diagram for M4 (example 3.12)
4 December -- Turing Machines. HW8: check language-device correctness from the other group; use Turing Machine Simulator and modify the code M4.txt (see the dropbox folder) to also work for empty words (accept #1#10#; #1#10##00; reject #1##10#, ##1#10##00)
11 December -- Undecidability. HW9: 3.9, 3.14, 4.2, 4.13 (select 3 out of 4 tasks)
18 December -- P and NP, Turing
8 January -- Decidability - continuation
15 January -- Polynomial time, P and NP, NP-complete problems
22 January -- Review and repeat
29 January -- Exam

Exercises are taken from the book that you can find in the materials folder at the bottom of the page
Homeworks can be done individually or in pairs
Homeworks are always due at the next class. You can submit them via email, at the secretary or in person at the beginning of the class.
Homeworks are discussed at the beginning of the next class, so no late submissions are allowed. In case of illness please contact me personally.
Unless otherwise indicated, homework assignment numbers refer to exercises in the course book. The book is available if you are in the university network, individual pages can be printed out/saved.
If you submit via email, please observe the following rules:
- use either .phil.hhu address or my gmail address, but not the general university address.
- you file name should clearly indicate you name/names and the assignment number (e.g. Ex1-Zinova.pdf);
- inside the file, both you name and your Matrikelnummer should be provided (I usually print your exercises out)
- in the theme of the email, write "FLAT18 - Homework 1 by A (and B)". This will ensure that it does not get lost.

For both BN and AP:

For an AP: