Catalogue of Modules, University of Nottingham

G52MAL Machines and their Languages
(Last Updated:03 May 2017)

Year  10/11

Total Credits: 10

Level: Level 2

Target Students:  Part I undergraduate students in the School of Computer Science. Also available to students from other Schools with the agreement of the module convenor.  Available to JYA/Erasmus students.

Taught Semesters:

Spring Assessed by end of Spring Semester 

Prerequisites: None.

Corequisites:  None.

Summary of Content:  

This module is part of the Foundations of Computer Science theme in the School of Computer Science.

A series of abstract machines, classes of formal languages, and their relation is investigated, along with important practical applications of this theory, in particular language recognition (lexical and syntactic analysis). Ultimately the investigations touch on the question of what can and cannot be computed. Topics covered include: finite state machines, regular expressions, context-free grammars, push-down automata, parsing, and Turing machines.

Module Web Links:
  • Reading List
  • Method and Frequency of Class:

    ActivityNumber Of WeeksNumber of sessionsDuration of a session
    Lecture 12 weeks2 per week1 hour

    Activities may take place every teaching week of the Semester or only in specified weeks. It is usually specified above if an activity only takes place in some weeks of a Semester

    Further Activity Details:
    Plus three problem classes spread over ten weeks to cover non-assessed coursework.

    Method of Assessment: 

    Assessment TypeWeightRequirements
    Exam 1 75 2 hr written examination 
    Coursework 1 25 Problem sheets with theoretical and small programming problems 

    Dr H Nilsson

    Education Aims:  To make the students conversant with central concepts of formal language and automata theory, such as finite automata and context-free grammars, and their applications. To give an introduction to computability theory.

    Learning Outcomes:  Knowledge and Understanding: Uderstanding of the equivalence between machine types and language types, the nature of formal languages and their specification by grammars and other notations, the practical and theoretical relevance of machines that process strings from an alphabet of symbols as models of computation, and the fundamental limits on what is computable by any machine. Intellectual Skills: Apply and deploy mathematical ability, practices and tools; understand complex ideas and relate them to specific problems or questions. Professional Skills: Understanding and ability to apply techniques for language specification. Transferable Skills: The ability to use mathematics to solve problems.

    Offering School:  Computer Science

    Use the Back facility of your browser to return to the previous page.

    Module Catalogue Search for another module

    [UoN Welcome Page] Return to The University of Nottingham Welcome Page