2021/22 Undergraduate Module Catalogue
COMP2321 Formal Languages and Finite Automata
10 creditsClass Size: 500
Module manager: Dr Samuel Wilson
Taught: Semester 2 (Jan to Jun) View Timetable
Year running 2021/22
This module is not approved as a discovery module
Module summaryProgramming 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.
ObjectivesThis module introduces the fundamental concepts required to study complexity, the design and implementation of programming languages and compilers.
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.
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.
|Delivery type||Number||Length hours||Student hours|
|Private study hours||68.00|
|Total Contact hours||32.00|
|Total hours (100hr per 10 credits)||100.00|
Opportunities for Formative FeedbackProgress is monitored through tutorial worksheets, regular coursework
Methods of assessment
|Assessment type||Notes||% of formal assessment|
|In-course Assessment||Coursework 1||25.00|
|In-course Assessment||Coursework 2||25.00|
|In-course Assessment||Coursework 3||25.00|
|In-course Assessment||Coursework 4||25.00|
|Total percentage (Assessment Coursework)||100.00|
There will be 4 coursework's next year, each worth 25%. The topics will be as follows. • Coursework 1: Finite state machines & Regular Languages • Coursework 2: Pushdown machines & Context-free Languages • Coursework 3: Turing machines & Associated Languages • Coursework 4: Independent investigation
Reading listThe reading list is available from the Library website
Last updated: 15/03/2022 16:12:19
Browse Other Catalogues
- Undergraduate module catalogue
- Taught Postgraduate module catalogue
- Undergraduate programme catalogue
- Taught Postgraduate programme catalogue
Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD