module specification

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

MA4005 Logic and Mathematical Techniques or MA4001  Logic and Problem Solving or MA4030 Mathematical Proofs and CS4001 Programming or equivalent.

• Words, alphabets and languages. Operations on words and languages. Closure of languages.(LO1, LO2, LO5)
• Deterministic finite automata. DFAs as language recognisers. Equivalent DFAs. Completion of DFAs. The DFA Pumping Lemma. Simplification and minimisation of DFAs.Software Implementation. (LO2, LO3, LO4)
• Non-deterministic finite automata. Algorithm for converting NFAs to DFAs. Software Implementation. (LO2, LO3, LO4)
• Distinguishable and indistinguishable states. Union, catenation 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, LO4)
• Simplification of CFGs. Binary Form, Chomsky Normal Form. (LO1,LO2, LO3, LO4, LO5)
• Universal computational machines. Turing machines and the Halting Problem. (LO2)

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.

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 Design and construct software that satisfies a formal or informal specification
LO5 Evaluate the quality of their specification and implementation, and
their experiences of group work, the processes of producing their coursework and the product produced.

This module is assessed through a coursework and an exam.

Coursework is based on case studies where the requirements are provided through an informal description.  Both pieces of coursework will have a group work part to encourage communication, critical analysis and creative thinking, and an individual work part to assess the practical skills in developing software after formal specification. Both pieces of coursework are assessed by report, product and viva. The report will include a reflective element by each student on the operation of the group, their work within the group, the quality of the product and what they learnt and discovered

• Coursework  consists of producing a formal specification from the case study requirements and its implementation
• The exam assesses the students’ knowledge, understanding and use of formal specification and modelling and software implementation at the end of semester.

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.