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.
|Spring||Assessed by end of Spring Semester|
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:
|Activity||Number Of Weeks||Number of sessions||Duration of a session|
|Lecture||12 weeks||2 per week||1 hour|
Method of Assessment:
|Exam 1||75||2 hour written examination|
|Coursework 1||25||Problem sheets with theoretical and small programming problems.|
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.
Search for another module
Return to The University of Nottingham Welcome Page