Formal Languages & Automata - MAT00002H

«Back to module search

  • Department: Mathematics
  • Credit value: 10 credits
  • Credit level: H
  • Academic year of delivery: 2022-23

Related modules

Pre-requisite modules

Co-requisite modules

  • None

Prohibited combinations

  • None

Additional information

Prerequisite information: Students must have taken Pure Mathematics or Pure Mathematics Option 1 or another suitable course in Pure Mathematics

Module will run

Occurrence Teaching period
A Autumn Term 2022-23

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

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.

Indicative assessment

Task % of module mark
Closed/in-person Exam (Centrally scheduled) 100

Special assessment rules

None

Indicative reassessment

Task % of module mark
Closed/in-person Exam (Centrally scheduled) 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