Material treated at the lecture notes and exercise classes
Automata Theory, fall 2023
==========================================================
Lecture 1, Monday, 4 September, 2023:
* Section 1.4, Chapter 2 until Example 2.1
Exercise class 1, Wednesday, 6 September, 2023:
* Exercises 1.37, 1.36(a), 2.1(jk)
* Study the other parts of Exercise 2.1, and Exercise 2.2 yourself
Lecture 2, Monday, 11 September, 2023:
* Finished Section 2.1
* Section 2.2
* Section 2.4 until Example 2.31
Exercise class 2, Wednesday, 13 September, 2023:
* Exercises 2.10, 2.22(adf)
* Study Exercises 2.24, 2.26 yourself
Lecture 3, Monday, 18 September, 2023:
* Finished Section 2.4
* Section 2.3 until Example 2.22
Exercise class 3, Wednesday, 20 September, 2023:
* Exercises 2.27(adg), 2.13, 2.17, 2.15, 2.21 (abdh),
Lecture 4, Monday, 25 September, 2023:
* Finished Section 2.3
* Section 2.5 (details of proof Theorem 2.36 have not been discussed,
so they are no topic for exam; the construction itself IS an exam topic)
* Exercise 2.36
* Section 2.6
Exercise class 4, Wednesday, 27 September, 2023:
* Exercises 2.33, 2.37, 2.38(a), 2.40, 2.55(ac)
Exercise class 4.5, Wednesday, 4 October, 2023:
* Questions from the students
Lecture 5, Monday 9 October, 2023:
* Section 3.2
* Section 3.3, where
- inductive proofs of Theorem 3.17 and Theorem 3.18 have not been discussed,
so they are no topics for exam
- we treated a slightly different construction than in the proof of
Theorem 3.17, for eliminating Lambda-transitions. Learn this, slightly
different construction, rather than the construction from the book.
- and, of course, also learn the construction from Theorem 3.18
Exercise class 5, Wednesday, 11 October, 2023:
* Exercises 3.21, 3.22(def), 3.24, 3.37(b), 3.40(a)
* Extra exercise about inverting construction for eliminating
Lambda-transitions
Lecture 6, Monday 16 October, 2023:
* Sections 3.1, 3.4
* Brzozowski & McCluskey (Exercise 3.54)
Exercise class 6, Wednesday, 18 October, 2023:
* A selection of Exercises 3.7(acefgijklm), 3.1(ab), 3.2,
3.10 (about reverse = mirror language), 3.41(e), 3.42
* Exercise 3.51(a, variant with Brzozowski & McCluskey)
Lecture 7, Monday 30 October, 2023:
* Sections 4.1, 4.2
Exercise class 7, Wednesday, 1 November, 2023:
* Exercises 4.10(acefdd2), 4.12, 4.1(bcefg), 4.3(bc), 4.4
Lecture 8, Monday 6 November, 2023:
* Section 4.3
* Section 4.4 until (including) page 146
* Not really discussed, so no exam topic: proof of Theorem 4.17
* Exercise 4.45(b) (with induction)
Exercise class 8, Wednesday, 8 November, 2023:
* Exercises 4.9, 4.26(a), 4.27, 4.22, 4.28, 4.29(ab), 4.34, 4.36(bcefg),
4.38(d)
Lecture 9, Monday 13 November, 2023:
* Section 4.5
* Even/odd markings, chop markings
* Exercises 4.51, 4.52, 4.53
Exercise class 9, Wednesday, 15 November, 2023:
* Exercises 4.38, 4.53(c_ii), 4.49(a), 4.50(ab) ChNF, 4.54
* Extra exercise on a CFG for AEqB
* Question 6 from Exam 19 December, 2022
Lecture 10, Monday 20 November, 2023:
* Sections 5.1, 5.2
* Not discussed, so no exam topic: special closure pre(L)
Exercise class 10, Wednesday, 22 November, 2023:
* Exercises 5.2, 5.4, 5.5, 5.6(a), 5.10, 5.12
* Extra exercise: (D)PDA voor {a^i b^j c^k | 2i>j}
Lecture 11, Monday 27 November, 2023:
* Section 5.3
- inductive proofs of Theorem 5.18 and Theorem 5.23 have not been discussed,
so they are no topics for exam
* Section 5.4 until Theorem 5.28
* Exercise 5.21
Exercise class 11, Wednesday, 29 November, 2023:
* Exercise 5.18, 5.16, 5.17, 5.19, 5.25, 5.28(b), 5.34(a), 5.30
* Extra exercise: what is the language accepted by a given PDA
Lecture 12, Monday 4 December, 2023:
* Finished Section 5.4
- the inductive proof of Theorem 5.29 has not been discussed,
so it is no topic for exam
* Even if proofs have not been discussed (entirely), the constructions
themselves and the intuitive ideas behind them ARE exam topics
* Section 6.1 until the mid of page 211
Exercise class 12, Wednesday, 6 December, 2023:
* Exercises 5.32, 5.35, 6.4
Lecture 13, Monday 11 December, 2023:
* Section 6.2
- the inductive proof of Theorem 6.13 has not been discussed,
so it is no topic for exam; of course, the construction itself IS
an exam topic
* Section 6.3
Exercise class 13, Wednesday, 13 December, 2023:
* Exercises 6.2(abdeg), 6.5(acdg), 6.6, 6.9
* Extra exercise: Chomsky normal form with 1 variable
* Extra exercise: CFL for {a^i x y b^j}