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 and 12.10. at 10:15-12:00. They all will take place in room M1. Rescheduled homework session on Friday 14.12. at 10:15-12:00 in 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. First exam date is January 7, 2019.
- 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