Automata Theory and Formal Languages

Tentative course schedule

• 10 October -- No class due to sickness
• 17 October -- No class due to sickness
• 24 October -- Introduction, Mathematical preliminaries. Finite automata, Deterministic automata. HW1: exercises 1.3, 1.4 (e, g), 1.5d, 1.6 (g, h)
• 31 November -- NDFA, Regular languages, closure properties. HW2: 1.7b, 1.8b, 1.9b, 1.10b, 1.14, 1.15, 1.16, 1.20 b,c
• 7 November -- Pumping lemma for RL. HW3 (deadline 21.11): 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
• 14 November -- Context-free languages, Chomsky normal form. HW 4: 1.49; 1.46a; 1.53; 2.4 c, e; 2.6 b; + analysis of the grammar of your group, for those, who were not there: 2.14, 2.38, 1.46c
• 21 November -- Pushdown automata. Pumping lemma for PDA/context-free languages. HW 5: 2.15; 2.16; 2.30a (try!); Bonus (if you solve it correctly, you don't have to resubmit other problems with pumping lemma for RLs!): 1.46d
• 28 November-- Pumping lemma for PDA/context-free languages. Equivalence of PDAs and CFGs. HW6: 2.26, 2.30 d, 2.31, 2.36
• 5 December -- Church-Turing thesis, Turing Machines. HW7: provide a formal definition or a state diagram for M4 (example 3.12), 3.2d, 3.8 (you can test your code in the simulator, link at the bottom of the page).
• 12 December -- Undecidability. HW8: 3.6, 3.9, 3.14 + 3.22 (no submission, but please think about it and not just look up the answer!)
• 19 December -- Turing machines
• 9 January -- Decidability - continuation. P and NP. HW9: in-class presentation or a 1 page essay about one of the NP complete problems. If you were not present at the class, write an email to confirm the topic.
• 16 January -- Polynomial time, P and NP, NP-complete problems. HW10: 4.2, 7.32
• 23 January -- Blockchain, rest of the presentations, review and repeat
• 30 January -- Last questions (8:45-9:45). AP test (10:00-11:30) and BN test for those who want it

Homework Rules

• 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 "FLAT19 - Homework 1 by A (and B)". This will ensure that it does not get lost.

Grading

For both BN and AP:

• all homework submitted in a reasonable condition.

For an AP:

• Exam at the last class

Links