CS6055 - Formal Languages (2024/25)
Module specification | Module approved to run in 2024/25 | ||||||||||||
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 2024/25(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
The module will be taught by a series of lectures, supervised laboratory, self-study and in class practical exercises. The lectures will be used to formally introduce the concepts and principles. 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 to:
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://londonmet.rl.talis.com/lists/C808AD20-06FA-9C9B-4859-22A3D47E78E1.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.