CS6055 - Formal Languages (2026/27)
| Module specification | Module approved to run in 2026/27 | ||||||||||||
| Module title | Formal Languages | ||||||||||||
| Module level | Honours (06) | ||||||||||||
| Credit rating for module | 15 | ||||||||||||
| School | School of Computing and Digital Media | ||||||||||||
| Total study hours | 150 | ||||||||||||
|
|||||||||||||
| Assessment components |
|
||||||||||||
| Running in 2026/27(Please note that module timeslots are subject to change) |
|
Module summary
Finite automata or finite state machines (and their languages) are structures that can be used as abstract models for computational devices, capturing many of their essential features without the complications of hardware considerations. This module will enable students from the mathematics and computing areas to appreciate the powers and limitations of computers and will introduce them to some of the factors in complier design through development of some of the standard mathematical models of computational devices.
The aims of this module are:
· To introduce a range of models of computational devices.
· To investigate the expressive power of different models.
· To introduce the idea of decision problems in mathematics.
· To demonstrate that interesting decision problems in computer science will often be unsolvable
Prior learning requirements
MA4005 Logic and Mathematical Techniques or MA4001 Logic and Problem Solving or MA4030 Mathematical Proofs and CS4001 Programming or equivalent.
Syllabus
• Words, alphabets and languages. Operations on words and languages. Closure of languages. (LO1, LO2, LO4)
• Deterministic finite automata. DFAs as language recognisers. Equivalent DFAs. Completion of DFAs. The DFA Pumping Lemma. Simplification and minimisation of DFAs. (LO2, LO3)
• Non-deterministic finite automata. Algorithm for converting NFAs to DFAs. (LO2, LO3, LO4)
• Distinguishable and indistinguishable states. Union, concatenation, and closure of finite automata. Intersection of two FAs. (LO1, LO2, LO5)
• Introduction to regular expressions. Examples and notation. Converting FA to regular expressions and vice versa. Expressive power and equivalence of regular expressions and FAs. Using regular expressions in programming. (LO1, LO2, LO3)
• Context free grammars. Introduction and notation. Derivations and syntax trees. Ambiguity in CFGs. Expressive power of FAs and CFGs. PDA implementation. (LO2, LO3)
• Simplification of CFGs. Binary Form, Chomsky Normal Form. (LO1, LO2, LO3, LO4)
• Universal computational machines. Turing machines and the Halting Problem. (LO2
Balance of independent study and scheduled teaching activity
Topics will be introduced through appropriate mediums.
The supervised practical sessions and/or seminars will provide opportunities to apply and experiment with the ideas introduced. The students will also be required to undertake independent study, for example individual and group case studies, some of which will be part of the assessment for the module.
Learning outcomes
On completing the module, the student should be able:
LO1 Demonstrate understanding of the advantages of using formal specification and understanding of specifications written by others.
LO2 Develop formal specifications from informal problem statements
LO3 Describe and recognise the characteristics of major established architecture styles
LO4 Evaluate the quality of their specification and implementation, and their experiences of group work, the processes of producing their coursework and the product produced.
Bibliography
Online Reading List:
https://rl.talis.com/3/londonmet/lists/C97195D6-2495-D2DB-B4F3-41AF20BF9B06.html
Textbooks:
Core Text:
• Derick Wood, Theory of Computation, John Wiley & Sons (1987), ISBN 978-0471613091.
Recommended Text:
• Adam Brooks Webber. Formal Language: A Practical Introduction. Franklin, Beedle & Associates, Inc. (2011); ISBN: 9781590281970.