2019-03-13: In the lecture tomorrow I will present solutions to exercises from the exam from August 2016.
2019-03-04: In the exercise session tomorrow the following problems will (probably) be covered: the third basic exercise and the additional exercises numbered 1, 3, 4 and 5.
2019-03-03: The sixth and seventh assignments are now available.
2019-02-24: The fifth assignment is now available.
2019-02-19: A hint has been added for the second exercise of the fourth assignment.
2019-02-08: The third and fourth assignments are now available.
2019-02-07: Minutes from a meeting with student representatives.
2019-02-06: After discussion with the student representatives I have decided that, starting with the seventh quiz, you get two opportunities to take each quiz. Your score will be the maximum of the (at most) two scores.
2019-02-02: The second assignment is now available.
2019-02-01: Some students have received some help with the first assignment, and I want all of you to get (roughly) the same information.
In the proof of Exercise 2.2 you might want to show that #a(auavb) = 2 + #a(u) + #a(v). How do you prove this? This property follows from a lemma that you can perhaps prove by induction: ∀u, v ∈ Σ*.#′a(uv) = #′a(u) + #′a(v) (where #′a ∈ Σ* → ℕ is the function discussed below).
2019-01-31: Decided how to treat (some) scores obtained in previous years.
2019-01-30: For the set S from the first assignment, does it make sense to define a function in the following way?
f ∈ S → Bool
f(ε) = true
f(auavb) = f(v)
f(buavaw) = false
No, because we would have
true =
f(ε) =
f(a(b(ε)a(aab)a(ε))a(ε)b) =
f(abaaabaab) =
f(a(baa)a(baa)b) =
f(baa) =
false.
When defining the functions #a and #b ∈ S → ℕ I suggest that you first define functions #′a and #′b ∈ Σ* → ℕ by regular recursion on strings, and then define #a(w) = #′a(w) and #b(w) = #′b(w) (note that S ⊆ Σ*).
I have added a slide that discusses this problem (slide 6).
2019-01-29: Fixed some bugs in the slides for the fifth lecture.
2019-01-24: The deadline for the second quiz has been moved to Sunday (2019-01-27, 15:00).
2019-01-24: There is now a list of student representatives.
2019-01-22: There are now answers to the quizzes from the first two lectures.
2019-01-21: A bug on a slide used in the first lecture has been fixed. (See page 7.)
2019-01-21: There seems to be problems with access to Canvas for GU students. In case of problems GU students can submit quiz answers via email to me. The usual deadlines apply.
2019-01-08: The timetable has been changed.