Catalogue of Modules, University of Nottingham

G52LAC Languages and Computation
(Last Updated:03 May 2017)

Year  17/18

Total Credits: 10

Level: Level 2

Target Students:  Part I undergraduate students in the School of Computer Science only.

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

  Available to JYA/Erasmus students.

Taught Semesters:

SemesterAssessment
Spring Assessed by end of Spring Semester 

Prerequisites: None.

Corequisites:  None.

Summary of Content:  You'll investigate classes of formal language and the practical uses of this theory, applying this to a series of abstract machines ultimately leading to a discussion on what computation is, what can and cannot be computed, and computational complexity. You'll focus in particular on language recognition, but will study a range of topics including: finite state machines, regular expressions, context-free grammars, Turing machines, Lambda calculus. Practical applications includes parsing. This module builds on parts of G52ACE and introduces concepts which are important to understand the analysis of algorithms in terms of their complexity.

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

Method of Assessment: 

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

Convenor: 
Dr H Nilsson
Dr V Capretta

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:
Construction of finite automata, regular expressions, and context-free grammars and translation between equivalent notions.
Determine a language's place in the Chomsky hierarchy.
Use declarative tools to generate parsers and scanners.
Identify key issues in syntax definitions: ambiguity, associativity, precedence
Familiarity with notions of general computation, including Turing machines, the lambda calculus, the Church-Turing thesis, decidability, the halting problem
Define the complexity classes P and NP.
Explain the significance of NP-completeness and give illustrative examples of P vs. NP.

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