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


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 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):

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.

  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
  7. Topic: Chomsky hierarchy, context-sensitive grammars, L-systems


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