Languages and Computation
| Code | School | Level | Credits | Semesters |
| COMP2012 | Computer Science | 2 | 10 | Spring UK |
- Code
- COMP2012
- School
- Computer Science
- Level
- 2
- Credits
- 10
- Semesters
- Spring UK
Summary
Covers 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. Focuses on language recognition, but will study a range of topics including: finite state machines, regular expressions, context-free grammars and Turing machines. Practical applications include parsing.
Target Students
Available to Level 2 students in the School of Computer Science. This module is part of the Foundations of Computer Science theme in the School of Computer Science.
Classes
Activities may take place every teaching week of the Semester or only in specified weeks.
Assessment
- 25% Coursework 1: Continuous assessment, including written homework exercises. Possibly with some under invigilated in-class test conditions. Reassessment is 100% examination.
- 75% Exam 1 (2-hour): In person examination using ExamSys. Reassessment is 100% examination.
Assessed by end of spring semester
Educational 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 and precedence.
- Familiarity with notions of general computation, including Turing machines, the lambda calculus, the Church-Turing thesis, decidability and 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.