Formal Languages & Automata - MAT00002H

« Back to module search

  • Department: Mathematics
  • Module co-ordinator: Prof. Victoria Gould
  • Credit value: 10 credits
  • Credit level: H
  • Academic year of delivery: 2019-20

Related modules

Pre-requisite modules

Co-requisite modules

  • None

Prohibited combinations

  • None

Module will run

Occurrence Teaching cycle
A Spring Term 2019-20

Module aims

  • To introduce and study a special class of formal languages, called recognisable (or regular) languages.

  • To give 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.

Module learning outcomes

  • 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 and use Schuetzenberger's theorem.

Module content

[Pre-requisite modules: students must have taken Pure Mathematics or Pure Mathematics Option 1.]

Syllabus

  • Strings and formal languages.

  • Recognisable languages.

  • The syntactic monoid of a language.

  • Finite state automata (DFAs) and the languages they recognise.

  • How to tell if a language is not recognisable - the pumping lemma.

  • Nondeterministic finite state automata (NDAs) and the languages they recognise.

  • Minimal automata.

  • Rational languages and Kleene's theorem.

  • Monoids, submonoids, subgroups, monoid homomorphisms.

  • Schuetzenberger's theorem.

Assessment

Task Length % of module mark
University - closed examination
Formal Languages & Automata
2 hours 100

Special assessment rules

None

Reassessment

Task Length % of module mark
University - closed examination
Formal Languages & Automata
2 hours 100

Module feedback

Current Department policy on feedback is available in the undergraduate student handbook. Coursework and examinations will be marked and returned in accordance with this policy.

Indicative reading

M V Lawson, Finite Automata, Chapman and Hall



The information on this page is indicative of the module that is currently on offer. The University is constantly exploring ways to enhance and improve its degree programmes and therefore reserves the right to make variations to the content and method of delivery of modules, and to discontinue modules, if such action is reasonably considered to be necessary by the University. Where appropriate, the University will notify and consult with affected students in advance about any changes that are required in line with the University's policy on the Approval of Modifications to Existing Taught Programmes of Study.