Fall semester 2018
Automata and Formal Languages
Lectures (28 times)
- Periods 1 and 2 (4.9.-18.10.2018 and 30.10.-13.12.2018):
- 10:15-12:00 Tuesday (Room M1, Quantum)
- 12:15-14:00 Thursday (Room M1, Quantum)
- Exceptions: No lectures on 11.9. and 13.9. and 25.9. and 4.10. and 6.12. These will be rescheduled.
Homework sessions (13 times)
- Periods 1 and 2 (10.9.-15.10.2018 and 29.10.- 10.12.2018):
- 14:15-16:00 Monday (Room M1, Quantum)
- Exception: No homework on 10.9. This will be rescheduled.
The following additional Friday classes will replace the cancelled ones: On 7.9. at 12:15-14:00, and on 21.9., 28.9, 5.10, 12.10. and 30.11. at 10:15-12:00. They all will take place in room M1.
Course Web Page:
Instructor:
Textbook:
- No texbook. Lecture notes are posted on the course web page.
About homework:
- Presence is mandatory. Absence is permitted only if agreed with the lecturer (ask beforehand if possible).
- To pass the course, at least 25% of the homework problems must be completed. The more problems you solve, the more credit towards the final grade you get: You get demo class
- A, if you complete 70%-100%,
- B, if you complete 45%-70%,
- C, if you complete 25%-45%
of the given homeworks.
Midterms:
- Two midterms: Oct 24 at 2pm-5pm and Dec 19 at 9am-12noon.
- Not mandatory. The class requirements can also be satisfied by taking a single final exam.
- Registration though internet (NettiOpsu) is required at least one week before the exam.
- Both midterms (3 hours) consist of 4 problems, each of which has maximum score of 4 point.
- A minimum of 5 points is required in both midterms.
- Homework activity (demo class A, B or C) and the combined score of the two midterms determine the final grade according to the following table:
|
Final Grade
|
Demo class
|
|
A
|
B
|
C
|
|
1
|
13-14
|
14-15
|
15-16
|
|
2
|
15-18
|
16-19
|
17-20
|
|
3
|
19-22
|
20-23
|
21-24
|
|
4
|
23-27
|
24-28
|
25-28
|
|
5
|
28-32
|
29-32
|
29-32
|
Final exam:
- An alternative way to pass the class. One can take the exam more than once (even if one has passed the course) to improve the final grade.
- Registration though internet (NettiOpsu) is required at least one week before the exam.
- Anyone with democlass at least C has qualified to take the exam within one year.
- Exams (4 hours) consist of 5 problems, each of which has maximum score of 8 points.
- Homework activity (demo class A, B or C) and the score of the final exam determine the final grade according to the following table:
|
Final Grade
|
Demo class
|
|
A
|
B
|
C
|
|
1
|
17-18
|
18-19
|
19-21
|
|
2
|
19-23
|
20-24
|
22-26
|
|
3
|
24-29
|
25-30
|
27-31
|
|
4
|
30-34
|
31-35
|
32-36
|
|
5
|
35-40
|
36-40
|
37-40
|
Brief course outline
- Regular languages
- Finite automata, regular expressions
- Kleene theorem
- Pumping lemma
- Closure properties and decision algorithms
- State minimization, Myhill-Nerode theorem
- Context-free languages
- Grammars, parsing
- Normal forms
- Pushdown automata
- Pumping lemma
- Closure properties and decision algorithms
- Turing machines
- Recursive and recursively enumerable languages
- Universal Turing machines
- Undecidability of the halting problem (Turing)
- Reductions, other undecidable problems