2016/17 Undergraduate Module Catalogue
COMP2321 Formal Languages and Finite Automata
10 creditsClass Size: 120
Module manager: Dr Kevin McEvoy
Email: k.mcevoy@leeds.ac.uk
Taught: Semester 2 (Jan to Jun) View Timetable
Year running 2016/17
This module is not approved as a discovery module
Module summary
Different programming languages have been designed for different purposes. In this module you will look at a number of different languages and when they might be used, study the steps performed by interpreters and compilers and develop the lexical analysis, parsing and code generation components of a compiler for a simple language.Objectives
On completion of this module, students should be able to:- understand the term 'model of computation' and be familiar with a number of standard models
- understand the theory of automata and grammars, and its applications
- understand the basics of computability, and demonstrate the existence of undecidable problems.
Learning outcomes
On completion of the year/programme students should have provided evidence of being able to:
-demonstrate a broad understanding of the concepts, information, practical competencies and techniques which are standard features in a range of aspects of the discipline;
-apply generic and subject specific intellectual qualities to standard situations outside the context in which they were originally studied;
-appreciate and employ the main methods of enquiry in the subject and critically evaluate the appropriateness of different methods of enquiry;
-use a range of techniques to initiate and undertake the analysis of data and information;
-effectively communicate information, arguments and analysis in a variety of forms;
Syllabus
Regular languages: finite automata (DFA, NFA), regular expressions,
regular grammars, equivalence of models, Pumping Lemma for regular languages.
Context-free languages: context-free grammars, parsing and parse trees, ambiguity. The role of grammars in the definition of the syntax of programming languages, BNF.
Recursive languages: Turing machines, the Church-Turing thesis, recursive and recursively enumerable languages.
Computable and uncomputable functions; computable and uncomputable sets; undecidable problems, the Halting Problem, Rice’s Theorem.
Teaching methods
Delivery type | Number | Length hours | Student hours |
Lecture | 22 | 1.00 | 22.00 |
Tutorial | 11 | 1.00 | 1.00 |
Private study hours | 77.00 | ||
Total Contact hours | 23.00 | ||
Total hours (100hr per 10 credits) | 100.00 |
Opportunities for Formative Feedback
Progress is monitored through tutorial worksheets, regular courseworkMethods of assessment
Coursework
Assessment type | Notes | % of formal assessment |
Problem Sheet | PS 1 | 20.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 type | Exam duration | % of formal assessment |
Standard exam (closed essays, MCQs etc) | 2 hr 00 mins | 80.00 |
Total percentage (Assessment Exams) | 80.00 |
Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated
Reading list
The reading list is available from the Library websiteLast updated: 15/11/2016
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