Topics on Parsing and Formal Languages

Master course in CS, fall 2010

People:
Lecturer: Robert Brijder, rbrijder@...
Assistent lecturer: Frank Takes, ftakes@...

Description:
Selected topics on parsing, formal languages and automata. Based on the book Second Course in Formal Languages and Automata Theory by Jeffrey Shallit (see below).

This course is a continuation of the course Second Course in Formal Language Theory. Therefore, one cannot receive ECTS for both courses. e-Studiegids page

Schedule:
Wednesday Sep 8 - Dec 1, 11:15 - 13:00, room 403, Snellius.

Examination:
updated: Handing in solutions in LaTeX for exactly 7 exercises for each of the chapters 3 and 4, and exactly 5 exercises for chapter 5 (so 19 solutions in total). (Or: solve an open Research Problem.) Submit electronically to rbrijder {at} liacs.nl.

Grading:
The grade for each chapter is determined based on the difficulty of the exercises you chose and quality of your solutions. The final grade is the average over the three grades, where all grades should be at least 6 (although at most one 5 is allowed).

Deadlines:
November 5 for Chapter 3,
November 26 for Chapter 4, and
December 17 for Chapter 5.
Deadlines for Chapter 3 and 4 are chosen to be Friday 16 days after a particular chapter has been finished in class. For Chapter 5 it is 23 days.

No written exam.

Requirements:
Basic knowledge in Automata and Formal Languages.
(For example, Fundamentele Informatica 1 and 2 as taught in the Bachelor computer science in Leiden. Fundamentele Informatica 3 is no prerequisite, but it is recommended.)

Book:
Second Course in Formal Languages and Automata Theory,
by Jeffrey Shallit, Cambridge University Press, 2008,
ISBN-13: 9780521865722. amazon.com
The webpage of the book contains an errata.

Classes:
(1) 8 Sep: I. Review -- 1.3 regular languages, 1.4 finite automata, 1.5 context-free
(3) 15 Sep: I. (continued) slides (of both 8 Sep and 15 Sep)
(3) 22 Sep: No lecture.
(4) 29 Sep: III. Finite automata -- 3.2 quotients, 3.3 morphisms and substitutions slides
(5) 6 Oct: III. (continued) -- 3.1 Moore and Mealy, 3.4 advanced closure, 3.5 transducers, 3.6 two-way finite automata slides (updated!)
(6) 13 Oct: III. (continued) -- 3.7, 3.8 transformation automaton, matrices slides
(7) 20 Oct: III. (continued) -- 3.9, 3.10 Myhill-Nerode and algorithm, 3.12 partial orders and regular languages slides
(8) 27 Oct: IV. Context-free grammars and languages -- 4.1 Closure properties, 4.2 Unary context-free languages, 4.6 Parikh's theorem slides
(9) 3 Nov: IV. (continued) -- 4.3, 4.4 Ogden's lemma, 4.5 interchange lemma slides
(10) 10 Nov: IV. (continued) -- 4.5 (continued), 4.7 deterministic context-free languages, 4.8 linear languages slides (updated!)
(11) 17 Nov: V. Parsing and recognition -- 5.1, 5.2 Earleys method, 5.3 Top-down parsing slides
(12) 24 Nov: V. (continued) -- 5.4 Removing LL(1) conflicts, 5.5 Bottom-up parsing slides
(13) 1 Dec: No lecture.