Format
Self-paced
Status
Status: planned, not offered yet
Programme
Foundation programme · Semester 4
Term
Spring 2028
Credits
7 ECTS
Study hours
200
Prerequisites
MAT101-F26 Discrete Structures, CS232-F27 Data Structures and Algorithms II
Module leader
Dr. Ali Khudiyev
Email
ali.khudiyev@wosm.academy
Office hours
Monday–Friday, 10:00–17:00 (Baku time, UTC+4)
Language
English
Cost
Free

Module Overview

Theory of Computation asks what computers can do in principle and what they can do efficiently. It studies abstract models of computation, from finite automata to Turing machines, and the classes of languages they recognise. Finite automata, met briefly in Digital Design and Computer Architecture I, are treated here in full.

The module has three parts. Automata and formal languages covers regular and context-free languages, which underlie pattern matching, lexing and parsing. Computability shows that some problems, such as the halting problem, cannot be solved by any program. Complexity makes precise the distinction between tractable and intractable problems introduced in Data Structures and Algorithms II.

Aims

  • Introduce the standard mathematical models of computation and the relationships between them.
  • Show the limits of computation through rigorous proofs of undecidability.
  • Give a precise foundation for complexity classes and NP-completeness.
  • Develop your ability to write careful proofs about formal objects.

Learning Outcomes

After completing this course, you will be able to:

  1. LO1.
    Construct deterministic and nondeterministic finite automata and regular expressions, convert between them, and minimise automata.
  2. LO2.
    Prove that languages are not regular using the pumping lemma and the Myhill–Nerode theorem.
  3. LO3.
    Construct context-free grammars and pushdown automata, transform grammars into Chomsky normal form, parse with the CYK algorithm, and prove that languages are not context-free.
  4. LO4.
    Describe Turing machines and equivalent models, explain the Church–Turing thesis, and prove problems undecidable by diagonalisation and reduction.
  5. LO5.
    Place problems in complexity classes such as P, NP and PSPACE, and prove that problems are NP-complete by reduction.

Syllabus

UnitTopic
1Alphabets, words and languages; proof techniques revisited
2Deterministic finite automata
3Nondeterminism and the subset construction
4Regular expressions and Kleene’s theorem
5Non-regular languages: pumping lemma, Myhill–Nerode, minimisation
6Context-free grammars, derivations and ambiguity
7Chomsky normal form and the CYK algorithm
8Pushdown automata and their equivalence with context-free grammars
9Non-context-free languages; closure properties
10Turing machines and their variants
11The Church–Turing thesis; universal Turing machines
12Decidability and the halting problem
13Reductions; Rice’s theorem; the Post correspondence problem
14Time complexity and the class P
15The class NP and the Cook–Levin theorem
16NP-complete problems and reductions
17Space complexity: PSPACE and Savitch’s theorem
18Course Review & Exam

Teaching and Learning Methods

The module is self-paced. All materials are provided on Moodle. Each unit has a lecture and exercise sheets with constructions and proofs.

ActivityHours
Lectures36
Labs / Tutorials24
Independent study140
Total200

Assessment

Your knowledge will be assessed throughout the course with quizzes, exercise sheets and the final exam. The exam checks whether you can build automata and grammars for given languages, and whether you can write correct proofs of non-regularity, undecidability and NP-completeness.

ComponentWeightDueLOs
Quizzes20%ThroughoutLO1–LO5
Exercise sheets30%ThroughoutLO1–LO5
Final exam50%End of moduleLO1–LO5
Total100%

Reading List

Essential

  • M. Sipser: Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2012.

Recommended

  • J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006.
  • D. C. Kozen: Automata and Computability, Springer, 1997.
  • S. Arora, B. Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

Materials and Licence

Course materials are published under the Creative Commons Attribution-ShareAlike 4.0 licence unless stated otherwise. See wosm.academy/licence for details.

Policies

  • Attendance: Attendance is not mandatory. The module is self-paced, so you can study the materials when it suits you.
  • Late submissions: Work submitted after the deadline is penalised.
  • Academic integrity: All submitted work must be your own. See the Code of Conduct.

Free. No application needed. New to Moodle? See How to join.