Formal grammars
(November 2009, University of Wrocław, Poland)
The course presents formal grammars
from the perspective of their original application:
specification of syntax and parsing.
The lectures were given by Alexander Okhotin (in English),
with additional seminars
by Artur Jeż (in Polish).
The list of topics presented in the course is given below.
All classes took place at the Institute of Computer Science
of the University of Wrocław.
There were 8 lectures (18 total hours) and 2 seminars (4 total hours).
News

The second seminar shall take place on
Saturday, November 28,
12:15, room 310.
(homework 2)

If you have any questions,
please come to room 340 on Friday,
on Saturday or on Monday.

The examination shall take place on Monday,
in room 340 (more details below).
The preferred time is 16:1518:00,
but if you cannot make it,
you are welcome to come at 912 or at 1316.
There will be a cake after the exam.

Lecture notes for lectures 48 posted.
Contents of the course

Inductive definition of syntax.
Contextfree grammars: definitions by equations and by rewriting.
Limitations of contextfree grammars.
Extensions of contextfree grammars.
Complexity of parsing.
(Tuesday, November 17, at 18:1520:00, room 141;
slides)

Conjunctive grammars.
Two definitions and their equivalence.
Examples of grammars.
(Wednesday, November 18, at 18:1520:00, room 141)

Further examples of grammars.
Transformation of a conjunctive grammar to a normal form:
elimination of empty conjuncts, elimination of unit conjuncts.
Outline of the CockeKasamiYounger parsing algorithm.
(Thursday, November 19, at 17:0518:50, room 103)

Boolean grammars and their semantics.
Normal form of Boolean grammars.
The CockeKasamiYounger algorithm:
the Boolean grammars edition.
(Friday, November 20, at 16:1518:00, room 325;
lecture notes)

The bottleneck of the CockeKasamiYounger algorithm.
Parsing through matrix multiplication.
Strassen's method of multiplying matrices.
(Monday, November 23, at 16:1518:00, room 325;
lecture notes)

Unambiguous grammars.
Inherently ambiguous contextfree languages.
Parsing unambiguous Boolean grammars in square time.
(Tuesday, November 24, at 18:1520:00, room 141;
lecture notes)

Parsing contextfree languages by a Boolean circuit:
the BrentGoldschlagerRytter algorithm.
Implementation of the algorithm on a Turing machine.
The notion of a Pcomplete language,
Pcompleteness of the circuit value problem.
A Boolean grammar for a Pcomplete language.
(Wednesday, November 25, at 9:1512:00, room 310;
lecture notes)

Recursive descent parsing for contextfree grammars,
and its generalization for conjunctive and Boolean grammars.
Ensuring linear time complexity.
Limitations of the recursive descent.
Generalized LR parsing for contextfree, conjunctive and Boolean grammars.
(Thursday, November 26, at 18:1521:00, room 103;
lecture notes)
Homework

Homework
for the first seminar
(Saturday, November 21, at 12:15, room 310).

Homework
for the second seminar
(Saturday, November 28, at 12:15, room TBA).
Examination
This is going to be an oral exam.
Each student will get
one randomly chosen theoretical topic
among those presented in the course,
and one randomly chosen problem
not harder than those considered at the seminars.
About 1530 minutes will be given for preparation,
and then the student is expected to tell
as much as possible on that topic,
as well as present a solution to the problem.
A few additional smaller questions may be asked
and additional problems may be given.
If the resulting mark does not satisfy the student,
it may be refused,
and will in this case be omitted from the records
as if the exam did not take place.
A cake will be provided.
Eligibility criterion:
every student who has attended to at least one lecture
OR has successfully passed the examination
is entitled to a piece.
Email: .