MAU11602 Computation theory and logic

Module Code	MAU11602
Module Title	Computation theory and logic
Semester taught	Semester 2
ECTS Credits	5
Module Lecturer	Prof. John Stalker
Module Prerequisites	MAU11201 Single-variable calculus

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..

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.

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.