Please note that this module can be taken by 4th year students as a 10 credit module with the module code 0590208.

 Aims

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.

Learning objectives

At the end of the module you should be able to:

• know and be able to use the basic definitions associated with monoids;
• use the monoid criterion for recognisability;
• determine the language recognised by a given finite state automaton;
• construct a finite state automaton to recognise a given recognisable language;
• use the pumping lemma to show that a non-recognisable language is not recognisable;
• determinise a given nondeterministic finite state automaton;
• minimise a given finite state automation;
• know and use Kleene's theorem;
• find the multiplication table of the syntactic monoid of a recognisable language;
• know Schutzenberger's theorem.

Syllabus

The following topics will be covered, not necessarily in this order.

• Strings and formal languages;
• Monoids, submonoids, subgroups, monoid homomorphisms;
• Recognisable languages;
• The syntactic monoid of a language;
• Finite state automata and the languages they recognise;
• How to tell if a language is not recognisable - the pumping lemma;
• Nondeterministic automata and the languages they recognise;
• Minimal automata;
• Rational languages and Kleene's theorem;
• Schutzenberger's theorem.

Recommended texts

M V Lawson, Finite Automata, Chapman and Hall (S 9.9 LAW) 

J M Howie, Automata and Languages, Clarendon Press (S 9.9 HOW)

Teaching

• Autumn Term
• 2 Lectures per week
• 1 Problems Class per week

Assessment

Two hour closed examination in Week 1 of Spring Term (100%)

Elective information

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.

Prerequisites

• Foundational material from Core Algebra
• A few very basic ideas from   Introduction to Group Theory, such as the definition of a group.