Languages and Automata (NWI-IPC002), 3rd quarter, 2019-2020
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 and weekly homework 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 4 February 17:00 (in Nijmegen).
-
Most groups will have their exercise class at 13:30. There is one group at 15:30 - this is only meant for people from different studies, who can't make it at 13:30 due to scheduling issues. All first year computing science students should register for a group at 13:30.
-
Do not register for a group which already has the maximum number of students, listed in the title. In that case, we have to do some reallocations (so note that it might happen that you end up in a different group after all).
- Lectures take place in LIN 2 on Tuesdays 13:30 - 15:15. The first
lecture is on February 4, and the last one on March 17.
-
Exercise classes (werkcolleges)
take place on Wednesday afternoon 13:30 (except for one group at 15:30).
- Lectures will be in taught in English.
- The final exam will be held on 30 March 2020, 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. Web lectures will be made available in brightspace.
- Slides, which are being produced as the course proceeds. Can be found in brightspace.
- Languages and Automata lecture notes, written
by Alexandra Silva, with some modifications;
these can be found in brightspace, and will be uploaded after each lecture.
-
Lecture 1, Tuesday 4 Feb, 13:30 - 15:15, LIN 2
- Topic: Regular Languages: words, operations on words,
languages, regular languages, regular expressions, proofs by
induction.
-
Lecture 2, Tuesday 11 Feb, 13:30 - 15:15, LIN 2
- Topic: Deterministic finite automata (DFA): Accepting
words, accepting a language, from DFAs to regular expressions.
-
Lecture 3, Tuesday 18 Feb, 13:30 - 15:15, LIN 2
- Topic: Non-deterministic finite automata (NFA): Accepting
words, accepting a language, removing non-determinism; from NFAs to
DFAs, from regular expressions to NFAs.
-
No lecture on 25 Feb.
-
Lecture 4, Tuesday 3 March, 13:30 - 15:15, LIN 2
- Topic: Non-regular languages, distinguishability, minimisation, closure
properties of regular languages.
-
Lecture 5, Tuesday 10 March, 13:30 - 15:15, LIN 2
- Topic: Grammars: Context Free and Regular Grammars
-
Lecture 6, Tuesday 17 March, 13:30 - 15:15, LIN 2
- Topic: Push-down automata: from CF grammars to push-down
automata and back.
-
Question hour, Tuesday 24 March, 13:30 - 15:15, HG00.303
-
Recap, and time for questions.
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 will be published here in brightspace on the day of the
lecture. It has to be handed in before the next Friday 17:00.
You must submit individually.
The graded work will be given back to you and will be
discussed at the exercise class on the Wednesday 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) start Wednesday 5 Feb.
Locations of the exercise classes are as follows:
- Group Dor Alter, HG00.058, 13:30-15:15
- Group Menno Bartels, HG00.065, 13:30-15:15
- Group Joris den Elzen, HG00.308, 13:30-15:15
- Group Maris Galesloot, HG01.028, 13:30-15:15
- Group Bas Hofmans, HG02.028, 13:30-15:15
- Group Serena Rietbergen, HG02.032, 13:30-15:15
- Group Marie-Sophie Simon, HG02.052, 13:30-15:15
- Group Jana Wagemaker, HG03.085 13:30-15:15
- Group Nienke Wessel, HG03.632, 13:30-15:15
- Group Amber Pater, HG00.308, 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, or upload a pdf to brightspace. All further details can be
read from a pdf with homework exercises, which is posted every Tuesday
in brightspace.
- 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
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, in July. If you fail once again, you will
have to redo the whole course (including exercises) next year.
The exam takes place on March 30, 2020 (check your schedule for time and place).
Material: everything (slides, notes, what was written on the board during the lectures).
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).
Since 2018-2019, this is not part of the material; instead, try to answer those questions with the distinguishable-word
technique that you learned.