## Table of Contents## MODULE DESCRIPTIONS## FLT - Formal Language Theory |

Lectures: 18 × 50-minute lectures.

Practicals: 0 × 1-hour practicals.

Private study: 69 hours.

Assessment: 3 hours.

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

Open: none.

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.

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.

**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;
*L*1 < *L*R < *L*0;
the workspace theorem.

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

**Affix grammars:**

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

+++ |
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 |