Accessibility statement

# 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: 2021-22

## Related modules

• None

### Prohibited combinations

• None

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 cycle
A Autumn Term 2021-22

## 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.

## Assessment

Task Length % of module mark
Online Exam
Formal Languages & Automata
N/A 100

None

### Reassessment

Task Length % of module mark
Online Exam
Formal Languages & Automata
N/A 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.