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


Dates, Time and Location

Course Material

Lectures Overview

Exercises and homework

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:

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.

  1. Topic: Languages, regular languages and regular expressions.
  2. Topic: Deterministic finite automata (DFAs), product construction, from DFAs to regular expressions.
  3. Topic: Non-deterministic finite automata and equivalence with deterministic finite automata.
  4. Topic: Minimisation and non-regular languages.
  5. Topic: Context Free Grammars and Regular Grammars
  6. Topic: Push-down automata


The final grade is based on: 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.