Table of Contents

FLT - Formal Language Theory

FLT - Formal Language Theory

Lecturer(s): AJF; Part: CS IIIa

See also:   compsci3.html

Workload

Lectures: 18 × 50-minute lectures.
Practicals: 0 × 1-hour practicals.
Private study: 69 hours.
Assessment: 3 hours.

Assessment

Closed: an unseen 90-minute paper (worth 50 marks): answer 2 questions (25 marks each) from 4.

Open: none.

Description

The Finn Alfred Aho has called Formal Language Theory ``the flower of Computer Science''. By this, he meant that FLT is not only a beautiful mathematical theory, but also a topic of central importance in computer science: compiler design, automata theory, complexity theory and the study of programming languages (to name but a few) are all aspects of computer science which depend upon and grow out of FLT, just as the petals of a flower grow out of its centre.

Aims

Students who successfully complete this course will have a set of well-focussed skills which will be invaluable to them in their careers, whatever they may be. These skills include the ability to digest and profit from closely-reasoned logical arguments; the ability to reconcile different aspects of a single theory, explained in ways which at first sight appear incompatible; and the ability to see the formal structure behind everyday concepts such as unsolvability and language equivalence.

Content

General: what is FLT?; languages and grammars; Backus-Naur form; the Chomsky classification.

Regular grammars and languages: matrix representation; regular functions & expressions; left-linear and right-linear grammars; closure properties; the self-embedding theorem; the pumping lemma.

Context-free grammars and languages: the uvwxy theorem; closure properties.

Context-sensitive grammars and languages: recursive and recursively-enumerable languages; parsability; L1 < LR < L0; the workspace theorem.

Van Wijngaarden grammars: definition; properties; parsability; predicates; examples from Algol 68.

Affix grammars:

Teaching material

Problem sheets and lecture notes will be distributed throughout the course. Copies of OHP slides may be purchased.

Recommended books

+++ Salomaa A., Formal Languages, Academic Press (1973)
Further details
++ Pagan F.G., Formal Specification of Programming Languages: a Panoramic Primer, Prentice Hall (1981)
Further details
** Rayward-Smith V.J., A First Course in Formal Language Theory, Blackwell Scientific (1983)
Further details
** Revesz G.E., Introduction to Formal Languages, McGraw-Hill (1985)
Further details

Last modified: Thu Dec 4 15:03:53 1997