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
- 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.