Languages and Machines, 2014/15, period IIb

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

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.

Evaluation and Assessment

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.

Material for the 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.

Week Schedule

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