Talen en Automaten (NWI-IPC002), lectures, 2nd quarter, Fall 2017

General information on this course can be found in Osiris. Please don't forget to register for this course, in order to receive (email) announcements. Relevant course information will be provided here (and not in blackboard), and by email. All course material will be in English.

The lectures will be given by Jurriaan Rot. Lectures will be on Tuesday morning, 8:45-10:30. The first lecture will be on November 14, and the last one on January 16.

Exercise classes (werkcolleges) take place on Friday morning 8:45 (except for Science (10:45) students; and two classes at 15:45, primarily for 'HBO-instromers' and double bachelor). Information about exercises and classes will be given on a separate exercise page.

Prerequisites consist of (secondary) school mathematics.

Course material consists of:

Everything the teachers write on the blackboard during the lectures.
Slides, which are being produced as the course proceeds. See below.
Languages and Automata Lecture notes called LnA below, written by Alexandra Silva, with some additions by Herman Geuvers.

Your final grade for this course will be composed from the half-way test grade, T1, the final test grade, T2, and the assignment grade, A.

weekly exercises are compulsory to hand in: your answers will be marked each week, and at the end of the course we compute the average of your marks; this average will constitute the assignment grade A. You must submit individually (not in pairs), see the exercise page for the exercises;
the half-way test on Tuesday December 12, 8:30-10:30 constitutes your half-way test grade T1.
the final test on Monday January 22, 8:30-11:30 constitutes your final test grade T2.
the final grade for the course is the average of the 2 test grades plus 10% of the assignment grade (with a maximum of 10):
min(10, (T1+T2)/2 + A/10).

If you fail, you can take the "hertentamen", which is a written exam about all the material, later on. If you fail once again, you will have to redo the whole course (including exercises) next year.

Schedule

lecture 1, Tuesday 14/11, 8:45 - 10:30, SP2
- Topic: Regular Languages: words, operations on words, languages, regular languages, regular expressions, proofs by induction.
- Lecture notes: Chapter 1 and Section 2.1.
- Slides: pdf
lecture 2, Tuesday 21/11, 8:45 - 10:30, SP2
- Topic: Deterministic finite automata (DFA): Accepting words, accepting a language, from DFAs to regular expressions.
- Lecture notes: Sections 2.2 and 4.2.2.
- Slides: pdf
lecture 3, Tuesday 28/11, 8:45 - 10:30, SP2
- Topic: Non-deterministic finite automata (NFA): Accepting words, accepting a language, removing non-determinism; from NFAs to DFAs, from regular expressions to NFAs.
- Lecture notes: Chapter 3, Section 4.1, Section 4.2.
- Slides: pdf
lecture 4, Tuesday 5/12, 8:45 - 10:30, SP2
- Topic: Non-regular languages: Pumping lemma, closure properties for the class of regular languages.
- Slides: pdf
Test 1, Tuesday 12/12, 8:30 - 10:30.
- For practice exams, see the bottom of the page
- Make sure you are registered (for the final test in January, there is no separate registration for the first test)
- Be present at 8:15 at the very latest.
- Topic: Halfway Test on Lectures 1--3.
- Locations for the Test:
  - LIN2 and LIN3
  - Extra time: HG00.065, HG00.616
lecture 5, Tuesday 19/12, 8:45 - 10:30, SP2
- Topic: Grammars: Context Free and Regular Grammars
- Slides: pdf
- Additional material (parsing, pumping lemma for CFGs) will not be part of test 2
lecture 6, Tuesday 9/1, 8:45 - 10:30, SP2
- Topic: Push-down automata: from CF grammars to Push-down automata and back.
- Slides: pdf
lecture 7, Tuesday 16/1, 8:45 - 10:30, SP2
- Topic: Chomsky hierarchy: Context-Sensitive Grammars and recursive languages; Lindenmayer systems.
- Slides: pdf
Question time
- At the last exercise class.
Test 2, Monday 22/1, 8:30 - 10:30.
- For practice exams, see the bottom of the page
- Make sure you are registered
- Be present at 8:15 at the very latest.
- Topic: Test on Lectures 4--6.
- Locations for the Test:
  - HAL2
  - Extra time: HG00.071

Exam

The half-way test takes place on Tuesday December 12, 8:30-10:30. It covers the material of lecture 1-3.
The final test takes place on Monday January 22, 8:30-11:30. It covers the material of lecture 4-6. (so 7 is not part of the exam!)
The second chance (hertentamen) takes place on Tuesday May 1, 8:30-11:30. It covers the material of lecture 1-6 (so the material of both test 1 and test 2).
Practice exams from 2016--2017: test 1, solutions, test 2, solutions, retake exam, solutions. Note: in 2016 the pumping lemma (lecture 4) was part of test 1, but this year it will be part of test 2!
Practice exams from 2015--2016: test 2, solutions.