Formal Grammars course, Spring 2009

The course, taught by Alexander Okhotin, aimed to present formal grammars as a mathematical theory, but with an emphasis on their original application: specification of syntax and parsing. The list of topics presented in the course is given below.

All classes took place at the Department of Mathematics of the University of Turku. In period III (12.1.-), the lectures took place on Tuesdays at 10-12 in MS-3 and on Wednesdays at 14-16 in MS-0. There were demos on Thursdays at 14-16 in MS-4. In period IV (2.3.-) the lectures were on Tuesdays at 10-12 and on Fridays at 14-16, with demos on Thursdays at 14-16; all classes were in MS-0.

News

Introduction

The first lecture gave a general outlook on formal languages and an overview of the course.

Finite automata

(1 1/2 lectures) Formal languages, operations on them. Finite automata and regular expressions. Simulation of nondeterminism. Equivalence of regular expressions and finite automata. Pumping lemma for regular languages.

Lecture notes
Homework 1 (due on January 21).

Basics

Turing machines. Undecidable problems. Reductions. Complexity of computation. Computational complexity classes. Basic decision problems for finite automata and their complexity.

Lecture notes
Homework 2 (due on February 12).

Context-free grammars

Definitions by rewriting and by language equations. Examples. Parse trees. Ambiguity. Pumping lemma. Closure properties (union, intersection, star, complementation, intersection with regular languages, homomorphism, cyclic shift). Decision problems (emptiness, membership, universality, emptiness of intersection).

Lecture notes 4 (version 5 March)
Homework 3 (due on February 19).

Intersections of context-free languages

Semilinear sets and Parikh's theorem. Bounded context-free languages. Infinite hierarchy of intersections.

Lecture notes 5.

Conjunctive grammars

Definitions by rewriting and by language equations. Examples: {wcw | w \in \{a,b\}^*}, {a4n | n >= 0}. Parse trees. Binary normal form. Cubic-time recognition.

Lecture notes 6 (version 24 March).
Homework 4 (due on March 12).
Homework 5 (due on March 19).

Boolean grammars

Intuitive definition. Examples. Language equations of the general form. Semantics of a strongly unique solution. Well-founded semantics. Binary normal form. Cubic-time recognition.

Lecture notes 7 (version 24 March).
Homework 6 (due on March 26).

Ambiguity

Unambiguous context-free, conjunctive and Boolean grammars. Inherently ambiguous context-free languages. Parsing in time O(n2).

Lecture notes 8 (version 27 March).
Homework 7 (due on April 2).

Theoretical complexity of parsing

Boolean grammars in space O(n). Context-free grammars by circuits of depth O(log2n), and in space O((log2n)2). Boolean grammars in time o(n3): as fast as matrix multiplication.

Lecture notes 9 (version 12 April).

Linear grammars and trellis automata

Linear context-free, linear conjunctive and linear Boolean grammars. Trellis automata (one-way real-time cellular automata) and their basic properties. Equivalence of linear conjunctive and linear Boolean grammars to trellis automata. Examples. Limitations.

Lecture notes 10 (version 14 April).
Homework 8 (due on April 16).
Homework 9 (due on April 23).

Practical parsing algorithms

Recursive descent for context-free, conjunctive and Boolean grammars. Limitations of the recursive descent. Pushdown automata and LR parsing.

E-mail: christian_name.family_name@utu.fi.