Languages and Computation
| Code | School | Level | Credits | Semesters |
| COMP2040 | Computer Science | 2 | 10 | Spring Malaysia |
- Code
- COMP2040
- School
- Computer Science
- Level
- 2
- Credits
- 10
- Semesters
- Spring Malaysia
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, Turing machines, Lambda calculus. Practical applications include parsing. Introduces concepts which are important to understand the analysis of algorithms in terms of their complexity.
Target Students
Available to Level 2 students in the School of Computer Science. Available to inter-campus mobility students and other exchange students in computer science. This module is not available to students not listed above, without explicit approval from the module convenor(s). This module is part of the Foundations of Computer Science theme in the School of Computer Science.
Classes
- One 1-hour tutorial each week for 10 weeks
- One 2-hour lecture each week for 11 weeks
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.
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 (2-hour): 2 hrs written examination. Reassessment is 100% 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 Tomas Henrique Bode Maul