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

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, 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)

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

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.

•The exam assesses the students’ knowledge, understanding and use of formal specification and modelling 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.