Introductory description

The module introduces methods used to describe and reason about formal languages (such as programming languages).
This module is only available to students in the second year of their degree and is not available as an unusual option to students in other years of study.

Module aims

The module presents a classification of formal languages (Chomsky hierarchy) and techniques for locating languages within it (closure properties, pumping lemmas). Automata models corresponding to various levels of the Chomsky hierarchy are discussed along with the fundamental notion of computability. These concepts are central to computer science.

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

Regular languages: finite automata, non-determinism, regular expressions, pumping lemma, non-regular languages, minimisation, translations between automata and regular expressions, closure properties
Context-free languages: context-free grammars, ambiguity, Chomsky normal form, pushdown automata, pumping lemma, translations between automata and grammars, closure properties
Introduction to lexical analysis and parsing
Turing-recognisable languages: Turing machines, Church-Turing thesis, decidability, reducibility, the halting problem

Learning outcomes

By the end of the module, students should be able to:

Specify formal languages.
Translate between various forms of formal language descriptions.
Argue that given formal languages are (or are not) regular or context-free.
Understand the operation of tools for lexical analysis and parsing.
Understand ideas of decidability and the Church-Turing thesis.

Indicative reading list

Please see Talis Aspire link for most up to date list.

View reading list on Talis Aspire

Subject specific skills

Formally describing, reasoning about and comparing various computational models. Applied in the study of complexity of computational problems.
Designing basic tools for lexing and parsing. Applied in the design of compilers.

Transferable skills

Critical Thinking - Problem-solving, rigorous analysis of possible solutions.

Study time

Type	Required
Lectures	30 sessions of 1 hour (20%)
Seminars	9 sessions of 1 hour (6%)
Private study	111 hours (74%)
Total	150 hours

Private study description

Working on weekly exercise sheets.
Background reading between lectures.
Exam revision and solving old/sample exam papers.

Costs

No further costs have been identified for this module.

You do not need to pass all assessment components to pass the module.

Students can register for this module without taking any assessment.

Assessment group D4

	Weighting	Eligible for self-certification
Programming assignment	20%	Yes (extension)
Online class test - Multiple choice	10%	Yes (waive)
45 Minute multiple-choice online test. The students may take the online test from a location of their choosing. The test will commence at the same time for all students.
In-person Examination	70%	No
Resit examination Answerbook Pink (12 page)

Assessment group R3

	Weighting	Study time	Eligible for self-certification
In-person Examination - Resit	100%		No
Resit examination Answerbook Pink (12 page)

Feedback on assessment

Individual written feedback on each assignment.

Past exam papers for CS259

Courses

This module is Core for:

Year 2 of UCSA-G500 Undergraduate Computer Science
UCSA-G503 Undergraduate Computer Science MEng
- Year 2 of G500 Computer Science
- Year 2 of G503 Computer Science MEng
Year 2 of UCSA-I1N1 Undergraduate Computer Science with Business Studies
Year 2 of UCSA-G4G1 Undergraduate Discrete Mathematics
Year 2 of UCSA-G4G3 Undergraduate Discrete Mathematics

This module is Option list B for:

Year 2 of USTA-G300 Undergraduate Master of Mathematics,Operational Research,Statistics and Economics

CS259-15 Formal Languages