Skip to main content Skip to navigation

CS259 Formal Languages

CS259-15 Formal Languages

Academic year
24/25
Department
Computer Science
Level
Undergraduate Level 2
Module leader
Dmitry Chistikov
Credit value
15
Module duration
10 weeks
Assessment
Multiple
Study location
University of Warwick main campus, Coventry
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 D4
Weighting Study time
Programming assignment 20%
Online class test - Multiple choice 10%

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%

Resit examination


  • Answerbook Pink (12 page)
Assessment group R3
Weighting Study time
In-person Examination - Resit 100%

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:

  • UCSA-G500 Undergraduate Computer Science
    • Year 2 of G500 Computer Science
    • Year 2 of G500 Computer Science
  • UCSA-G503 Undergraduate Computer Science MEng
    • Year 2 of G500 Computer Science
    • Year 2 of G503 Computer Science MEng
    • Year 2 of G503 Computer Science MEng
  • Year 2 of UCSA-I1N1 Undergraduate Computer Science with Business Studies
  • UCSA-G4G1 Undergraduate Discrete Mathematics
    • Year 2 of G4G1 Discrete Mathematics
    • Year 2 of G4G1 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

Further Information

Term 2

15 CATS (7.5 ECTS)

Online Material

Note: 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.