Formal Languages and Automata
Course category:3rd year
Please note that this module can be taken by 4th year students as a 10 credit module with the module code 0590208.
The aim of the course is to introduce and study a special class of formal languages called recognisable (or regular) languages. A formal language is a collection of finite sequences (known as strings or words) of symbols from a finite set. For example, the symbols might be 0 and 1; then, an example of a formal language would be the set consisting of all strings with an even number of 1s.
There are a number of equivalent definitions of the notion of recognisable language, some involving an algebraic structure called a monoid, some involving devices called finite state automata, and one purely combinatorial definition. Most of the course will be devoted to showing that these different approaches give the same class of formal languages.
The flavour of the course is algebraic, but with plenty of illustrative examples.
At the end of the module you should be able to:
The following topics will be covered, not necessarily in this order.
M V Lawson, Finite Automata, Chapman and Hall (S 9.9 LAW)
J M Howie, Automata and Languages, Clarendon Press (S 9.9 HOW)
Two hour closed examination in Week 1 of Spring Term (100%)
Available as an elective. Please check prerequisites carefully before asking to take this module as an elective. In choosing this module as an elective it will be assumed that you are familiar with much of the material taught in the module Core Algebra and some of that from Introduction to Group Theory, or are willing to learn the material if necessary.
Department of Mathematics, University of York, Heslington, York, UK. YO10 5DD