Finite Automata is a fundamental module in theoretical computer science that introduces the mathematical models of computation and their applications in problem-solving and language processing. This module focuses on the study of abstract machines and the computational problems that they can solve. Students will learn how to design, analyse, and implement finite automata to recognise regular languages and perform pattern matching.

This module focuses on the study of Regular Languages within the context of Automata Theory. Regular languages form the foundation of formal language theory and are closely linked with Finite Automata. The module covers the theoretical underpinnings of regular languages, their characterisation through finite automata and regular expressions, and the practical applications in areas such as compiler design, pattern matching, and text processing. Students will explore how to manipulate regular languages and prove their properties and limitations.

This module introduces the concept of Context-Free Languages (CFLs) and their fundamental role in the theory of computation and formal language theory. It covers the theoretical foundations, practical applications, and formal representation of CFLs through Context-Free Grammars (CFGs). Students will explore how CFLs are generated, manipulated, and analysed using derivation trees, parse trees, and normal forms such as Chomsky Normal Form (CNF) and Greibach Normal Form (GNF). The module also examines key properties of CFLs, including ambiguity, the pumping lemma for CFLs, and closure properties. Practical applications in programming languages, syntax analysis, and compiler design are also discussed.

This module introduces key techniques for simplifying context-free grammars (CFGs), including the removal of useless, nullable, and unit productions. It also covers the transformation of CFGs into normal forms, such as Chomsky Normal Form (CNF) and Greibach Normal Form (GNF), which are essential for parsing and algorithmic applications. Additionally, the module explores fundamental properties of Context-Free Languages (CFLs), including closure properties, the pumping lemma, and decision problems.

This module introduces the Turing Machine, a fundamental theoretical model of computation. It covers the formal definition of a Turing Machine, its components, and its functioning as a computational device. Students will explore different approaches to designing Turing Machines and work through design examples to understand their applications. The module also examines the dual role of Turing Machines: As a language acceptor to recognise formal languages and as a transducer to compute functions, demonstrating their significance in theoretical computer science and the foundations of computation.

This module explores advanced concepts and variations of the Turing Machine, a cornerstone of computational theory. It delves into Turing Machines with finite control, multiple tracks, two-way infinite tapes, multi-tape configurations, multi-head mechanisms, and non-deterministic models, highlighting their unique capabilities and computational power. The concept of the Universal Turing Machine is introduced, demonstrating its role as a model of general computation. The module also examines Turing-computable functions and their implications, culminating in an understanding of the Church-Turing Thesis, which formalises the limits of algorithmic computation and the foundations of computer science.

This module examines the classification of formal languages and their relationship to computational models. It focuses on recursive and recursively enumerable languages, exploring their properties and distinctions within the computational framework. The concept of unrestricted grammars is introduced as a powerful tool for generating languages beyond regular and context-free classes. Additionally, the module delves into context-sensitive grammars (CSG) and their place in the Chomsky Hierarchy, providing a structured understanding of language classes and their computational complexity. These topics form the foundation for analysing the expressive power of different formal systems and their real-world applications.

This module, part of Automata Theory, focuses on the foundational concepts of computability and decidability. Students will study formal languages, automata models (finite automata, pushdown automata, Turing machines), and the classification of computational problems based on their solvability. The module examines how Turing machines serve as a standard for what is "computable" and explores the limits of algorithmic problem solving through examples of decidable and undecidable languages. Students will engage in formal reasoning, proofs, and reductions to understand the theoretical boundaries of computation.

This module, integrated into Automata Theory, introduces the study of computational complexity, understanding not just what problems can be solved, but how efficiently they can be solved. Students will explore models of computation, such as Turing machines, to analyse time and space complexity. The course covers complexity classes like P, NP, and NP-complete problems, with a focus on formal methods to prove complexity bounds. Through examples and theoretical proofs, students will develop the ability to evaluate the efficiency of algorithms and the intrinsic difficulty of computational problems.