This module aims to introduce the formal mathematical foundations of computer science. Students will study the hierarchy of automata, grammars, and formal languages and investigate the ultimate theoretical limits of computation. This module provides the essential theoretical backbone for the information and computing science curriculum. The foundational knowledge of formal languages is a prerequisite for advanced studies. The rigorous proof techniques developed here are crucial for subsequent modules such as Complexity of Algorithms. By covering the concept of undecidability, the module frames the universal constraints explored in fields like Artificial Intelligence and advanced theoretical computing.
A.Examine the relationships between language as an object recognised by an automaton and as a set generated by a formal grammar. B.Apply standard translations between equivalent automata and grammars. C.Analyze the limitations (with respect to expressive power) of different automata (including Turing machines) and grammar forms. D.Differentiate between decidable and recognisable languages. E.Classify the membership of concrete languages by applying formal arguments.
Students will be expected to attend two hours of formal lectures as well as to participate in two hours of supervised problem classes in a typical week. Lectures will introduce students to the academic content and practical skills which are the subject of the module, while problem classes will allow students to practice those skills. In addition, students will be expected to devote 7 or 8 hours of unsupervised time to solving continuous assessment tasks and private study. Private study will provide time for reflection and consideration of lecture material and background reading. Continuous assessment will be used to test to what extent practical skills have been learnt.