Languages and Computation
| Code | School | Level | Credits | Semesters |
| COMP2049 | School of Computer Science | 2 | 10 | Spring China |
- Code
- COMP2049
- School
- School of Computer Science
- Level
- 2
- Credits
- 10
- Semesters
- Spring China
Summary
You will 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 will 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 AE2ACE and introduces concepts which are important to understand the analysis of algorithms in terms of their complexity.
Target Students
Part I undergraduate students in the School of Computer Science only.
Classes
- One 1-hour workshop each week for 12 weeks
- One 2-hour lecture each week for 12 weeks
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.
Assessment
- 25% Coursework 1: Problem sheets with theoretical and small programming problems.
- 75% Exam 1 (2-hour): 2 hour written examination
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: Discuss the concept of finite state machines. Design a deterministic finite state machine to accept a specified language. Generate a regular expression to represent a specified language. Determine a language's place in the Chomsky hierarchy. Convert among equivalently powerful notions for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs. 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, and the Lambda calculus. Explain the Church-Turing thesis and its significance. Explain how programs that process other programs treat the other programs as their input data. Explain why the halting program has no algorithmic solution. Provide examples of incomputable functions. Define the complexity classes P and NP. Explain the significance of NP-completeness. Illustrative examples of P vs NP such as graph isomorphism. 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.
Conveners
- Dr Amin Farjudian