Module and Programme Catalogue

Search site

Find information on

2018/19 Undergraduate Module Catalogue

COMP2321 Formal Languages and Finite Automata

10 creditsClass Size: 220

Module manager: Dr Kevin McEvoy
Email: k.mcevoy@leeds.ac.uk

Taught: Semester 2 (Jan to Jun) View Timetable

Year running 2018/19

This module is not approved as a discovery module

Module summary

Programming and programming languages are essential tools for computer science practitioners. The theory and technology that underpins the development of programming languages, in the past and the present, is that of formal languages and finite automata. This module exists to provide a solid foundation of formal languages and finite automata which will be built on in subsequent modules. This module focuses on the formal specification of languages, the corresponding hierarchy of abstract machines and contributes to developing an understanding of design considerations of programming languages.

Objectives

This module introduces the fundamental concepts required to study complexity, the design and implementation of programming languages and compilers.

Learning outcomes
On successful completion of this module a student will have demonstrated the ability to:

- recall definitions and theorems relating to formal languages and finite automata and apply them appropriately.
- describe and compare different models of computation.
- articulate the existence of undecidable problems.
- illustrate the applications of formal languages and finite automata in the fields of programming language design and compilers.


Syllabus

This module covers the following 3 topic areas:

- Formal languages : regular languages, context-free languages, recursive languages, recursively enumerable languages, grammars, Backnus Naur form (BNF), parsing and parse trees.
- Abstract models of computation : finite automata and Turing machines (both deterministic and non-deterministic).
- Computability : computable and uncomputable functions, computable and uncomputable sets, undecidable problems, the Halting problem, Rice's theorem.

Teaching methods

Delivery typeNumberLength hoursStudent hours
Lecture221.0022.00
Tutorial101.0010.00
Private study hours68.00
Total Contact hours32.00
Total hours (100hr per 10 credits)100.00

Opportunities for Formative Feedback

Progress is monitored through tutorial worksheets, regular coursework

Methods of assessment


Coursework
Assessment typeNotes% of formal assessment
Problem SheetPS 120.00
Total percentage (Assessment Coursework)20.00

Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated


Exams
Exam typeExam duration% of formal assessment
Standard exam (closed essays, MCQs etc)2 hr 00 mins80.00
Total percentage (Assessment Exams)80.00

This module is re-assessed by exam only

Reading list

The reading list is available from the Library website

Last updated: 04/10/2018

Disclaimer

Browse Other Catalogues

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD

© Copyright Leeds 2019