CS259-15 Formal Languages
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 | Study time | 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
|
|||
Assessment group R3
| Weighting | Study time | Eligible for self-certification | |
|---|---|---|---|
| In-person Examination - Resit | 100% | No | |
|
Resit examination
|
|||
Feedback on assessment
Individual written feedback on each assignment.
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