It is likely that this page will be modified frequently during the course.
Last modified: 24 June 2015
New: Available is the exam of June 18, with a set of solutions, see below.
The time for the exam discussion on 8 July has been changed.
Lecturer
Wim H. Hesselink
(Bernoulliborg 374).
Teacher of the tutorials:
Jasper van de Gronde.
Schedule of the course.
The course consists of lectures, tutorials, and homework. It is
not enough to understand the material. You must be able to work with
it, to apply it creatively, i.e., to solve the exercises on your own.
You can only learn this by trying it. This is the purpose of the
tutorials and the homework. Also, when you have made an exercise, you
must be able to evaluate your own solution in a critical way. Of
course, during the tutorials the teacher is there to assist you in
finding a solution, and in evaluating solutions proposed. The weekly
homework is evaluated by the lecturer, and marked with a grade that
counts a little bit in the final grade of the course. You are allowed
to make and turn in the homework in pairs (which then get the same
grade). You may discuss the homework with fellow students. It is not
allowed to turn in copies of homework from fellow students.
The course uses the lecture notes "Languages and Machines", that can
be obtained at the Repro of the Bernoulliborg. For Dutch students who
want to be able to talk about the subject matter in Dutch,
a
glossary is made available. I am not able to do this for other
languages.
The course has a size of 5 EC. It is concluded by a written examination. The final grade is obtained as a weighted average of the examination grade and the homework grades, where the examination grade counts for 80 %, and the homework counts for 20 % (in this sense the homework is obligatory). The homework does not count anymore at the re-examination.
The course material as defined in the week schedule below, together with the exercises chosen for the tutorials and the homework.
Available is the exam of 18 June 2015 and a corresponding set of solutions. Also available is an English translation of the examination of July 2014.
The material for each lecture is indicated by sections in the
Lecture Notes. The notation C 2 [2, 3, 5] means Sections 2, 3, and 5
of Chapter 2. Read the text as a preparation of the lecture.
Afterwards, read it again to see whether you fully understand it. Ask
questions about the text in the lecture or in the tutorials.
The notation C 1.3 (1, 6) indicates the exercises 1 and 6 of Section
1.3. The goal is that you are able to make the exercises on your own,
but you need not expect this to work in the beginning. It will be
asked from you at the examination.
There are six homework assignments. Make them on your own or in
pairs. Turn it in on paper in the post box of Hesselink
(Bernoulliborg, 4th floor North, behind the elevator), usually on
Friday morning before 10 AM. In this homework, every assertion or
design must be argued carefully to enable me to understand it, and to
correct and grade it.
Week 1 (16). Tuesday 14 April. Overview of the course,
mathematical notations, fundamental concepts of formal languages,
regular expressions. Lecture Notes C 1 en C 2 [1, 2].
Wednesday 15 April. Tutorial: C 1.3 (1, 2, 3, 6a),
2.5 (1, 2, 3, 4, 6, 7, 8).
Thursday 16 April. Context-free grammars and
context-free languages, Lecture Notes C 2.3.
Friday 17 April before 10 AM. Homework 1: Lecture Notes C 1.3 (4, 9),
2.5 (5, 10).
Week 2 (17).
Tuesday 21 April. Normal forms of context free grammars,
Lecture Notes C 2.4.
Wednesday 22 April. Tutorial: C 2.5 (11, 15bd, 17, 21, 24, 30).
Thursday 23 April. Finite state machines, Lecture Notes C 3 [1, 2].
Friday 24 April before 10 AM. Homework 2: C 2.5 (14, 23a, 25).
Week 3 (18). Tuesday 28 April. Finite state
machines, regular expressions and regular languages, Lecture Notes C 3
[3, 4, 5].
Wednesday 29 April. Tutorial: C 3.9 (3, 5, 9, 12, 13, 16, 17, 19ac).
Thursday 30 April. Closure properties of regular languages, the pumping lemma,
after languages and own languages, Lecture Notes C 3 [6, 7, 8 (1, 2)].
Friday 1 May before 10 AM. Homework 3: C 3.9 (2, 11c, 15).
Week 4 (19). Tuesday 5 May. No Lecture (liberation day).
Wednesday 6 May. Tutorial: C 3.9 (21, 25, 26b, 27, 28, 29).
Thursday 7 May.
Pushdown machines and context-free languages, Lecture Notes C 4.1
Friday 8 May before 10 AM. Homework 4: C 3.9 (20c, 22).
Week 5 (20).
Tuesday 12 May. The context free pumping lemma, closure
properties of context free languages, Lecture Notes C 4 [2, 3].
Wednesday 13 May. Tutorial: C 4.5 (2, 3ad, 6, 7b).
Thursday 14 May. No Lecture (ascension day).
Week 6 (21).
Tuesday 19 May. Turing machines, Lecture Notes C 5 [1, 2].
Wednesday 20 May. Tutorial: C 5.9 (1c, 2c, 3, 5, 7, 9).
Thursday 21 May. More about Turing machines. C 5 [3, 4, 5, 6, 8].
Friday 22 May before 10 AM. Homework 5: C 4.5 (3e, 7f), C 5.9 (2d).
Week 7 (22). Tuesday 26 May. Decidability,
Lecture Notes C 6 [1, 2].
Wednesday 27 May. Tutorial: C 6.9 (1, 2, 3, 4, 6, 7, 9).
Thursday 28 May. The Universal Turing Machine, decidability
and undecidability, C 6 [2, 3, 4, 5].
Friday 29 May before 10 AM. Homework 6: C 5.9 (11) en C 6.9 (8, 12a).
Week 8 (23).
Tuesday 2 June. Decidability and undecidability, C 6 [6, 7, 8].
Wednesday 3 June. Tutorial: C 7.4 (1, 2, 3). Parts of the examination
of July 2014, see above.
Thursday 4 June. Unrestricted and context-sensitive grammars, and
the Chomsky hierarchy, Lecture Notes C 7.
Examination: Thursday 18 June 2015, 14:00-17:00.
Examination discussion, Wednesday 8 July, 12:30-13:30.
Please, inform me of errors, inconsistencies, or mistakes in the above or
in the Lecture Notes.
Back to my
education page or my home page. Wim H. Hesselink