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**

Proofs

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

**Regular languages**

Definition

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