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.
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; L1 < LR < L0; the workspace theorem.
Van Wijngaarden grammars: definition; properties; parsability; predicates; examples from Algol 68.
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)
Pagan F.G., Formal Specification of Programming Languages: a Panoramic Primer, Prentice Hall (1981)
Rayward-Smith V.J., A First Course in Formal Language Theory, Blackwell Scientific (1983)
Revesz G.E., Introduction to Formal Languages, McGraw-Hill (1985)