Automata Theory and Formal Languages

Important current information:

• HW8 are checked and will be available (as well as all old assignments) for pick-up at the secretary on 14/12.
• HW9 can be found below as Exercise sheet, ex. 1 and 2 should be submitted by the next class (either in a written form or in oral form);
  ex 3 can be submitted at any point until the end of the course, but only in oral form (if you absolutely can't come, we can make a Skype appointment).
  The same rule applies to the exercises with respect to PDAs, they are also uploaded below.
  Group submissions are possible as long as each group member can explain every step of the proof.
• There total maximum of points for all homework assignments will be around 200.

Tentative course schedule

• 10 October -- Introduction, Set theory. Poll.
  Homework: ex. 1 (2 points), 3 (3 points), 4 (8 points), 5 (3 points) in Chapter 1. Note a typo in ex. 4c: it should be once union and once intersection and not 2 times union.
• 17 October -- Relations, functions, alphabet, string, formal language, graphs and trees (1.2-1.6)
  Homework: ex. 7 (2 points), 8 (4 points), 10 (3 points), 11 (3 points), 17 a, b (4 points) in Chapter 1.
• 24 October -- Theorem proving, Finite automata - 1. Homework: ex. 4 (2 points), 5 (3 points), 6 (2 points), 12 (6 points), 30 (4 points) in Chapter 2. Homework is due by 7.11
• 7 November -- Finite automata - 2. Poll. Homework (total 18 points). +You may resubmit 12b from HW3!
• 14 November -- Regular Languages and Regular Grammars - by Simon Petitjean. Poll. Homework (total 17 points).
• 21 November -- RL and RG - 2, Context Free Grammars and Context Free Languages - 1. Homework (total 19 points).
• 28 November -- Context Free Grammars and Context Free Languages - 2. Homework (total 16 points).
• 5 December -- CFG-3, Greibach Normal Form, Pumping lemma, Decision problems for CFLs. Homework (total 20 points). Hint: Some pumpung lemma applications
• 12 December -- CFG-4. Exercises (aka HW9, 20 points): CFG,
• 19 December -- Push-down Automata, Exercises (aka HW10, 24 points): PDA
• 9 January -- Turing Machines, Decidability. Homework (total 16 points).
• 16 January -- Time complexity. P and NP. NP-completeness. Homework for 10 bonus points: read about two problems that are NP-complete or NP-hard and tell about them on Jan 23.
• 23 January -- Space complexity.
• 30 January -- Exam

Homework Rules

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

Grading

For both BN and AP:

• 50% of points for Homeworks

For an AP:

• Klausur at the last class