MAU11602 Computation theory and logic
Module Code | MAU11602 |
---|---|
Module Title | Computation theory and logic |
Semester taught | Semester 2 |
ECTS Credits | 5 |
Module Lecturer | Dr. Nicolas Aidoo |
Module Prerequisites | MAU11201 Single-variable calculus |
Assessment Details
- This module is examined in a 2-hour examination at the end of Semester 2.
- Continuous assessment contributes 30% towards the overall mark.
- The module is passed if the overall mark for the module is 40% or more. If the overall mark for the module is less than 40% and there is no possibility of compensation, the module will be reassessed as follows:
1) A failed exam in combination with passed continuous assessment will be reassessed by an exam in the supplemental session;
2) The combination of a failed exam and failed continuous assessment is reassessed by the supplemental exam;
3) A failed continuous assessment in combination with a passed exam will be reassessed by one or more summer assignments in advance of the supplemental session..
Contact Hours
11 weeks of teaching with 3 lectures per week.
Tutorials will be held during the lecture time slots and a revision will take place at the end of the semester.
Learning Outcomes
On successful completion of this module, students will be able to
- check the validity of statements in zeroeth and first order logic.
- convert informal statements to formal statements in elementary arithmetic.
- give semiformal proofs in zeroeth and first order logic, elementary arithmetic and set theory.
- verify the correctness of formal proofs in zeroeth and first order logic, elementary arithmetic and set theory.
- convert informal descriptions of languages into phrase structure grammars.
- convert among regular grammars, deterministic and non-deterministic finite state automata and regular expressions.
- apply the Myhill-Nerode theorem to check whether languages are regular.
- apply the pumping lemmas to show languages are not regular or context free.
- apply the various closure properties of regular and context free languages.
Module Content
- Formal languages and phrase structure grammars.
- Zeroeth order logic, also known as the propositional calculus.
- First order logic.
- Elementary arithmetic.
- Gödel's and Tarski's theorems.
- Axiomatic set theory, and finite, countable and uncountable sets.
- Finite state automata, regular expressions and regular languages.
- Pushdown automata and context-free languages.
- Turing machines and recursively enumerable languages.