Theory of Computing

Course Code: 
Credit Points: 

Course Outline

Theory of Computation contains three central areas: automata, computability and complexity. These areas are linked by the following important question: What are the fundamental capabilities and inherent limitations of computers?

This question is interpreted differently in each of these three areas and corresponding answers are shaped accordingly. In the context of computability theory, the goal is to characterize the various problems as solvable or not. In complexity theory, the goal is to categorize solvable problems into easy and difficult and the central question is: What is it that makes some problems computationally hard and some other easy? One of the most important achievements of complexity theory is an elegant system of classifying problems according to their computational hardness.

This course essentially focuses on automata theory which deals with the definitions and properties of mathematical models of computation. These models are used in practice in several areas of computer science. For example, finite automata are used in string searching and pattern matching, word processing, compiler and hardware design. Another model, context-free grammars, is used in programming languages and artificial intelligence. Automata theory is a particularly interesting area that allows practice with formal definitions of computation which are highly significant in the theory of computability and complexity where a precise definition of the computer is required.

Lectures proceed according to the following sections:

Set theory


Sets, operations, alphabets, strings, languages, operations with languages

Regular languages


Model of computation: finite automata (DFA, NFA)

Finite representation: regular expressions

Equivalence of finite automata with regular expressions

Closure properties of regular languages

Non-regular languages

Context-free languages

Model of computation: (non-deterministic) pushdown automata

Finite representation: context-free grammars

Equivalence of (non-deterministic) pushdown automata with context-free grammars

Closure properties of context-free languages

Non-context-free languages

Church-Turing thesis

Model of computation: Turing machine

Finite representation: algorithms

Startup Growth Lite is a free theme, contributed to the Drupal Community by More than Themes.