NWI-MOL090 Formal Languages, Grammars and Automata, Q.4 2013

Teacher
Contents
Examination
Schedule
Material

Teacher

Lectures: Herman Geuvers: home page
Exercise Classes: Nico Broeder and Jasper Derikx.

In theoretical computer science there is a strikingly simple definition of language. One starts with an alphabet Sigma, a finite set of symbols. With these symbols one forms arbitrary strings: these are the words over Sigma. This set is denoted by Sigma*. A language is obtained by determining by one or another way a subset of Sigma*, consisting of words that are 'useful' for a particular context. One can do this via syntactic production (so called "grammars"), but also by machine recognition (using so called "finite automata"). For two classes of languages this will be done.

The regular languages, produced by a simple mechanism, and the corresponding finite automata.
For context-free languages, with a different production mechanism, and the corresponing stack-automata, having a simple kind of memory.

In the sciences also language-like phenomena play an important role. Genetic code and programming languages are examples.

Subjects

Alphabet, string, language, grammar, finite automaton, stack-memory, determinism, non-determinism.

Examination

Wriiten exam, "closed book"; dates:
TENTAMEN Tuesday, 8:30 -- 11:30, week 26, LIN 5
HERTENTAMEN Thursday, 16:30 -- 19:30, week 32, HG00.071

There is a test (halfway the course) and a written exam. The grade t of the test only helps in a positive way getting a good grade for the course. If T is the grade for the 'Tentamen', then the final grade F is F=max{1/2(t+T),T}, if T is at least a 5, ontherwise T.

Schedule

The course consists of 2 hours hoorcollege" FRIDAY, 13:45--15:30 HG00.304, plus 2 hours werkcollege (exercise class) on FRIDAY, 15:45--17:30 in HG00.633, HG00.065.

Every week, one exercise can be delivered with Nico Broeder or Jasper Derikx by Tuesday noon, in the postbox with the names Jasper en Nico, immediately to the left when you enter wing HG03.7--. This will be given back at the next werkcollege.

The following gives the schedule.

April 19: Languages and Regular Languages:

Slides of lecture 1.
Exercises of lecture 1.
Solutions (in Dutch) of exercises of lecture 1.
Chapter 1 of Regular Languages and Finite Automata
April 26: Finite Automata and their languages:
- Slides of lecture 2.
- Exercises of lecture 2.
- Some hand written solutions of exercises of lecture 2 by Jasper and Nico,
- Some more hand written solutions of exercises of lecture 2 by Jasper and Nico,
- Section 2.1, Chapter 4 of Regular Languages and Finite Automata
May 17: Non-deterministic automata and regular languages:
- Slides of lecture 3.
- Exercises of lecture 3.
- Some solutions of exercises of lecture 3.
- Some hand written Solutions of exercises of lecture 3 by Jasper and Nico,
- Some more hand written solutions of exercises of lecture 3 by Jasper and Nico,
- Sections 2.2, 2.3, Chapter 3 of Regular Languages and Finite Automata
May 24: The pumping lemma and non-regular Languages:
- Slides of lecture 4.
- Exercises of lecture 4.
- Some hand written solutions of exercises of lecture 4 by Jasper and Nico,
- Some more hand written solutions of exercises of lecture 4 by Jasper and Nico,
- Sections 5.1 and 5.2 of Regular Languages and Finite Automata
May 31: First hour: Grammars. Second hour: Test over lectures 1--4; see under Examination. Here are the solutions to the test.

Slides of lecture 5.
Exercises of lecture 5.
Some hand written solutions of exercises of lecture 5 by Jasper and Nico,
Sections 6.1 and 6.2 of Regular Languages and Finite Automata

June 7: Regular and context-free grammars:
- Slides of lecture 6.
- Exercises of lecture 6.
- Some hand written solutions of exercises of lecture 6 by Jasper and Nico,
- Section 6.3 of Regular Languages and Finite Automata
June 14: Push-down automata:
- Slides of lecture 7.
- Exercises of lecture 7.
- Some hand written solutions of exercises of lecture 7 by Jasper and Nico.
June 21: Wrap-up of the course; L-Systems
- Slides of lecture 8.
- Exercises of lecture 8.
- Some hand written solutions of exercises of lecture 8 by Jasper and Nico.
- L systems

Material

Regular Languages and Finite Automata, Lecture Notes by Marcelo Fiore (Cambridge University Computer Laboratory).
NBThis is a set of lecture notes I found later and which I like much better than the notes by Ruohone, as they are much more extensive. It should be note that the notation is somewhat different, using "epsilon" for "lambda" and "|" for the union of two regular expressions.
Formal languages, Reader by K Ruohonen. At the course it will be announced which parts are relevant.

herman at cs dot ru dot nl