Formal Languages, Grammars and Automata (MOL090), lectures, 2nd quarter, Fall 2014
General information on this course can be found in the
Science
studiegids. Please don't forget to register in blackboard 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 Twan van Laarhoven, in Dutch, but all course
material will be in English. Information about exercises will be given
on a
separate
exercise page.
Lectures will be on Wednesday mornings, 8:45-10:30, in lecture hall HG00.068
in the Huygens building. The first lecture will be on November 12,
and the last one on January 14. The exam is on January 26.
Prerequisites consist of (secondary) school mathematics.
Course material consists of:
- Languages and Automata Lecture notes called LnA below, written
by Alexandra Silva
- Slides, which are being produced as the course proceeds.
| Order |
Topic |
File |
| 1 | Regular Languages |
pdf |
| 2 | Deterministic Automata |
pdf |
| 3 | Non-Deterministic Automata |
pdf |
| 4 | Non-Regular Languages |
pdf |
| 5 | Recap of first part and Test-Exam |
pdf |
| 6 | Context-Free Grammars and Regular Grammars |
pdf |
| 7 | Push-down Automata |
pdf |
| 8 | Context-Sensitive Grammars and the Chomsky hierarchy; Lindenmayer systems; Wrap up of the course |
pdf |
| 9 | Question time and old exam |
exam of Spring 2013. |
Some handwritten answers
(in Dutch) of the exam of Spring 2013. (No guarantees on full
correctness or legibility.) |
Your final grade for this course will be composed from
the assignment grade a, the half-way test-exam grade h and the final exam grade f:
- 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 7 marks; this average will constitute the assignment
grade a. The assignment grade a must be 6 or higher! You must submit
individually (not in pairs), see
the exercise
page for the exercises;
- the half-way test-exam (Wednesday December 10, not mandatory)
constitutes your half-way test-exam grade h.
- the final written exam (Monday January 26, 8:30-11:30, LIN 6)
constitutes your final exam grade f. This final exam grade f must
be 5 or higher.
- the final grade for the course is the maximum of f and (f+h)/2 increased with a/10.
If you fail, you can 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.
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.
Lectures schedule
- lecture 1, Wednesday 12/11
- Topic: Languages, regular languages and regular expressions.
- lecture 2, Wednesday 19/11
- Topic: Deterministic finite automata (DFAs), from regular expressions to DFAs.
- lecture 3, Wednesday 26/11
- Topic: Non-deterministic finite automata and equivalence with deterministic finite automata.
- lecture 4, Wednesday 3/12
- Topic: The pumping lemma and non-regular languages.
- lecture 5, Wednesday 10/12
- Topic: Wrap up of part I, followed by the half-way
test-exam during the exercise class hours.4, wrap
up and opportunity for questions on part I
- 10:30 -- 12:30: Half-way test-exam on part I [Note that this starts at 10:30 sharp]
- locations: HG00.310 (students [A--G]), HG00.206
(students [H--R]) and HG00.065 (students [S--W]) Note the extra room
and the room you have to go to!
- lecture 6, Wednesday 17/12
- Topic: Context Free and Regular Grammars
- lecture 7, Wednesday 7/1
- Topic: Push-down automata
- lecture 8, Wednesday 14/1
- Topic: Context-Sensitive Grammars and the Chomsky
hierarchy; Lindenmayer systems; Wrap up of the course.
- Question time: Friday 23/1, 13:30-15:30, HG.00.633
Exam
- The exam takes place on Monday January 26, 8:30-11:30 in LIN 6.
- The time and place of the second chance are not yet known.