• Student home
• Things to know this week
• Student news
• Student events
• New students' welcome
• Studying at York
  • Semesters
  • Teaching hours
  • Enrolment
  • Manage your studies
    • Enrol or re-enrol
    • Your student record
    • Your timetable
    • Change your plan
    • Programmes and modules
      • Programme specifications
      • Studying beyond your department
      • Module catalogue
    • University study spaces
  • Student Visa holders
  • Study skills
  • Assessment and examination
  • Academic progress issues
  • Graduation
• Support and advice
• Health and wellbeing
• Work, volunteering and career planning
• Study and work abroad
• Accommodation
• IT and online services
• Finance
• Student life in York
• If things go wrong
• Student Centre

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: 2022-23
  • See module specification for other years: 2021-22

Related modules

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.

Assessment

Task	Length	% of module mark
Closed/in-person Exam (Centrally scheduled) Formal Languages & Automata	2 hours	100

Special assessment rules

None

Reassessment

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