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