Talen en Automaten (NWI-IPC002), lectures, 2nd quarter, Fall 2016
General information on this course can be found in the
Informatica
studiegids. 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).
The lectures will be given by Herman Geuvers and Jurriaan Rot. All course material
will be in English. Information about exercises will be given on a
separate
exercise page.
Lectures will be on Tuesday afternoon, 13:45-15:30. The first lecture will be on November 8,
and the last one on January 10.
Prerequisites consist of (secondary) school mathematics.
Course material consists of:
- Languages and Automata Lecture notes called LnA below, written
by Alexandra Silva, with some additions by Herman Geuvers.
- Everything the teachers write on the blackboard during the lectures,
- Slides, which are being produced as the course proceeds. See below.
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 13, 13:30-15:30 constitutes
your half-way test grade T1.
- the final test (Wednesday January 18, 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.
All students who have already done the exam for this course twice,
unsuccesfully, will be required to do the following before they obtain
the right to do the exam again:
- Talk to the study advisor; it is advised to contact him/her as
soon as possible to schedule a meeting;
- Talk to the teacher to fill in a form;
- Attend all lectures and exercise classes.
Schedule
- lecture 1, Tuesday 8/11, 13:45-15:30, HG00:307,
- Topic: Regular Languages: words, operations on words,
languages, regular languages, regular expressions, proofs by
induction, Chapter 1 and Section 2.1.
- Slides: pdf
- lecture 2, Tuesday 15/11, 13:45-15:30, HG00:307
- Topic: Deterministic finite automata (DFA): Accepting
words, accepting a language, from DFAs to regular expressions, Sections 2.2 and 4.2.2.
- Slides: pdf
- lecture 3, Tuesday 22/11, 13:45-15:30, HG00:307
- Topic: Non-deterministic finite automata (NFA): Accepting
words, accepting a language, removing non-determinism; from NFAs to
DFAs, from regular expressions to NFAs.
- Slides: pdf
- lecture 4, Tuesday 29/11, 13:45-15:30, HG00:307
- Topic: Non-regular languages: Pumping lemma, closure
properties for the class of regular languages.
- Slides: pdf
- lecture 5, Tuesday 6/12, 13:45-15:30, HG00:307
- Topic: Grammars: Context Free and Regular Grammars
- Slides: pdf
- Test 1, Tuesday 13/12, 13:30-15:30.
- Here are test1 of 2015 and test2 of 2015, and here are the
answers, with the answer to 4c of test1 here separately. (Note: in 2015,
the "pumping lemma" was in test2, but in 2016 it is in test1.)
- Make sure you are registered for the course
- Be present at 13:15 at the very latest.
- Topic: Halfway Test on Lectures 1--4.
- Locations for the Test:
- names A -- G: HG00.307
- names H -- M: HG00.071
- names N -- Z: LIN 3
- extra time students: HG00.086
- lecture 6, Tuesday 20/12, 13:45-15:30, HG00:307
- Topic: Push-down automata: from CF grammars to Push-down
automata and back.
- Slides: pdf
- lecture 7, Tuesday 10/1, 13:45-15:30, LIN1
- Topic: Chomsky hierarchy: Context-Sensitive Grammars and
recursive languages; Lindenmayer systems.
- Slides: pdf
- Question time: Tuesday 17/1, 13:45-14:30 in HFML0220
- Topics: Question time, handing back assignment 7, old
assignments, old exam.
- The second test of 2015-2016, not
completely representative for the material of this year. (The Pumping
Lemma wasn't in test1; this year we also treated translations between
PDAs and CFGs.)
- Answers to the second test of 2015-2016.
Exam
- The half-way test takes place on Tuesday December 13, 13:30-15:30.
- the final test takes place on Wednesday January 18, 8:30-11:30.
- The second chance is: Wednesday March 1, 18:00-21:00.
- Here is the reexam of last year. Try it
under exam conditions (put away your notes, make it in 3 hrs). Here
is the reexam of last year
with answers.