Languages and Automata (NWI-IPC002), 2nd quarter, Fall 2018
Lecturer:
Jurriaan Rot.
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; weblectures, slides, notes, announcements are in brightspace.
All course material will be in English.
Contents of this course webpage
-
Please register for one of the exercise groups in Brightspace, before Tuesday 6th November 23:59.
-
There are two groups for Science students only (at 10:30), and two groups
for double bachelor, math and pre-master students at 15:30 (this info is in the title of the groups). Everyone else should register
for one of the 8:30 classes. For space reasons it's essential that you register for the right type of group!
-
Do not register for a group which already has the maximum number of students, listed in the title.
- Lectures take place in SP2 on Tuesdays 8:30 - 10:15. The first
lecture is on November 6, and the last one on December 18.
-
Exercise classes (werkcolleges)
take place on Friday morning 8:30 (except for Science (10:30) and pre-master (15:30) students).
- Lectures will be in taught in English.
- The final exam will be held on Friday 11 January 2019, 8:30-10:30.
- There are weekly homework assignments, with which
you can earn a bonus for your final grade.
- Everything the teachers write on the blackboard during the lectures.
- Slides, which are being produced as the course proceeds. Can be found in brightspace.
- Languages and Automata lecture notes, called LnA below, written
by Alexandra Silva, with some modifications;
these can be found in brightspace, and will be uploaded after each lecture.
-
Lecture 1, Tuesday 6/11, 8:30 - 10:15, SP2
- Topic: Regular Languages: words, operations on words,
languages, regular languages, regular expressions, proofs by
induction.
-
Lecture 2, Tuesday 13/11, 8:30 - 10:15, SP2
- Topic: Deterministic finite automata (DFA): Accepting
words, accepting a language, from DFAs to regular expressions.
-
Lecture 3, Tuesday 20/11, 8:30 - 10:15, 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 4, Tuesday 27/11, 8:30 - 10:15, SP2
- Topic: Non-regular languages, distinguishability, minimisation, closure
properties of regular languages.
-
Lecture 5, Tuesday 4/12, 8:30 - 10:15, SP2
- Topic: Grammars: Context Free and Regular Grammars
-
Lecture 6, Tuesday 11/12, 8:30 - 10:15, SP2
- Topic: Push-down automata: from CF grammars to Push-down
automata and back.
-
Lecture 7, Tuesday 18/12, 8:30 - 10:15, SP2
- Topic: Chomsky hierarchy: Context-Sensitive Grammars and
recursive languages; Lindenmayer systems.
-
Question hour, Tuesday 8/1, 10:30 - 12:15, MERC I 00.28
-
Time for questions; we'll also make a few
exercise from the retake exam of 2015-2016, combined with some
questions from the retake exam of last year, see here.
There are weekly homework exercises, which count as a bonus if you hand them in in time
(the average of your grade for the first six weekly assignments; the homework for lecture 7 is not graded).
The homework will be published here on the day of the
lecture. It has to be handed in before the next Tuesday 8:30 (lecture time), sharp!
You must submit individually.
The graded work will be given back to you and will be
discussed at the exercise class on the Friday after that.
In the schedule below, there will typically also be some additional exercises
to practice with, including solutions (these exercises are not graded).
Exercise classes (werkcolleges) take place on Friday morning 8:30 (except for Science (10:30) and pre-master + double bachelor (15:30) students). Exercise sessions start Friday 9/11.
Here are the locations of the exercise classes (please register for
one of the groups on Brightspace):
- Group Menno Bartels, HG00.065, 8:30-10:15
- Group Maris Galesloot, HG00.086, 8:30-10:15
- Group Leon Gondelman, HG00.114, 8:30-10:15
- Group Ellen Gunnarsdóttir, HG00.308, 8:30-10:15
- Group Toine Hulshof, HG00.633, 8:30-10:15
- Group Alexis Linard, HG00.310, 8:30-10:15
- Group Jan Martens, HG01.028, 8:30-10:15
- Group Serena Rietbergen, HG01.029, 8:30-10:15
- Group Bas Steeg (science), HG01.028, 10:30-12:15
- Group Nienke Wessel (science), E1.09 (Erasmus building!), 10:30-12:15
- Group Bas Hofmans (pre-master, double bachelor), HG00.308, 15:30-17:15
- Group Amber Pater (pre-master, double bachelor), HG00.310, 15:30-17:15
Handing in your answers: put them (handwritten or typed) into the
delivery box of your exercise class teacher on the ground floor
of Mercator 1. All further details can be
read from a pdf with homework exercises, which is posted every Tuesday
on this page.
- Topic: Languages, regular languages and regular expressions.
- Topic: Deterministic finite automata (DFAs), product construction, from DFAs to regular expressions.
- Topic: Non-deterministic finite automata and equivalence with deterministic finite automata.
- Topic: Minimisation and non-regular languages.
- Topic: Context Free Grammars and Regular Grammars
- Topic: Push-down automata
- Topic: Chomsky hierarchy, context-sensitive grammars, L-systems
- Exercises: pdf
- Exercise class: 21/12
- The last set of exercises is not graded. However, the topics are part
of the material for the exam! A model solution for the exercises is
here, so that you can
check your own work.
The final grade is based on:
- final exam (t)
- weekly homework assignments to be handed in; we compute the average
of the grades for the six assignments (h)
The final grade is min(t + (h/10),10), provided that t >= 5.
If you fail, you can take do a retry of the written exam later on. If you fail once again, you will
have to redo the whole course (including exercises) next year.
The exam takes place on January 11th, 2019 (check your schedule for time and place).
Material: everything (slides, notes, what was written on the board during the lectures),
except the second part of lecture 7 (on applications).
Also see the slides of lecture 6 in Brightspace for exam topics.
Below are some practice exams.
Be careful: in previous editions of the course, we used a different technique to prove languages to be non-regular (the pumping lemma).
In 2018-2019, this is not part of the material; instead, try to answer those questions with the distinguishable-word
technique that you learned.
Another point: context-sensitive languages are a part of the material this year; in previous years, they were not,
so in the practice exams there are no questions about them.