Formal Languages and Automata Theory (FLAT)

Tentative course schedule

• 6 November -- Introduction (live), Mathematical preliminaries: infinities. Finite state automata, Deterministic automata: good intro, Vending machine as a FSA, a cute intro to DFSA.
  HW1: exercises 1.3, 1.4 (e, g), 1.5d, 1.6 (g, h), 1.7 (c, e) - as we did not discuss intersection/complement, any solution is fine for 1.4 and 1.5. Recording of the meeting
• 13 November -- Closure properties of regular languages, DFA to RL, RL to FA, NDFA, equivalence of NFA and DFA.
  HW2: exercises 1.8a, 1.9b, 1.10a, 1.13, 1.14, 1.15, 1.17, 1.21b. Recording of the meeting
• 20 November -- Pumping lemma for regular languages (1), Pumping lemma for regular languages (2) (different videos for the same content)
  HW3: 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, don't submit these), 1.30, 1.31. Recording of the meeting
• 27 November -- Context-free languages, Chomsky normal form. Slides from Intro to CL are in Dropbox. Recording of the meeting (I forgot to turn it on at the beginning).
  HW4: 1.49, 1.71, 2.4b, c, 2.6b
• 4 December -- Pushdown automata (German), Pushdown automata (English). Pumping lemma for PDA/context-free languages (1), (2), example. Recording of the meeting
  HW5: 2.13, 2.14, 1.53, 1.54, 2.30a
• 11 December -- Equivalence of CFGs and PDAs (part 1), Equivalence of CFGs and PDAs (part 2), DCFLs, Context-Free Language Closure Properties.
  Recording for solutions for HW5 (1), (2), Recording of the lecture part
  HW6: 2.2a, 2.9, 2.26, 2.32, 2.48
• 18 Dezember -- Turing Machine.I really recommend you to watch either "The Imitation Game" (available on Amazon as Prime Video) or "Codebreaker" (should be available on Netflix) about Alan Turing.
  Turing Machine Examples, Definition of TMs, The Church-Turing Thesis Solutions HW6, Theoretical part.
  HW7: 2.21, 2.30d, 3.7, 3.8 b, 3.11 (due 15.01.2021)
• 8 January -- no class
• 15 January -- more Turing machines. Class recording HW8: the exercise listed on the simulator page under the code for the binary addition (Fibonacci sequence), 4.4, 4.8, 2.36, 2.42
• 22 January -- Time complexity. Class recording. HW9: 7.6, 7.8, 2.45
• 29 January -- P vs NP. Class recording. HW10: select an NP-complete problem and prepare a short presentation (what is the problem, how it is parametrised, examples, how to show NP-completeness) to share with others on Jan 5 (preferred!) or write a 1 page essay about this problem. Post the name of the selected problem in the RocketChat and do not take any problem that has been taken already. Only for those who did not write a Fibonacci TM: Round the (binary) number up to the nearest multiple of 3 (Task and a hint can be found under "divisible by three" machine on the simulator page).
• 5 February -- Start at 12:30! Class recording. NP-complete problems presentations. Space complexity. Wrapping-up game (aka last homework): challenge a fellow student with a language (to be continued in RocketChat, see description there).
• 12 February -- NP-complete problems presentations (if any left). Blockchain. Summary (take-away from the class), questionnaire (anonymous).

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 "FLAT20 - 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