Skip to main content Skip to navigation

Module Catalogue

CS259-15 Formal Languages

Department
Computer Science
Level
Undergraduate Level 2
Module leader
Ramanujan Maadapuzhi Sridharan
Credit value
15
Module duration
10 weeks
Assessment
Multiple
Study location
University of Warwick main campus, Coventry

Download as PDF

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

  1. Formally describing, reasoning about and comparing various computational models. Applied in the study of complexity of computational problems.
  2. 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

  1. Working on weekly exercise sheets.
  2. Background reading between lectures.
  3. 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 D3
Weighting Study time Eligible for self-certification
Programming assignment 20% Yes (extension)
Class Test 10% No

50 Minute class test
In-person Examination 70% No

Resit examination

  • Answerbook Pink (12 page)
Assessment group R1
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 Optional for:

  • Year 2 of USTA-G1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)
  • Year 2 of USTA-GG14 Undergraduate Mathematics and Statistics (BSc)

This module is Option list B for:

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