# Outline

This course is an introduction into the theory of computing. We will learn the fundamental language classes (regular, context-free grammar, general grammar) and their corresponding machine models (finite automata, pushdown automata, Turing machine). We will also discuss problems that are undecidable in these models. Finally, we will study complexity issues like NP-completeness.

The course is divided into four major topics.
First we introduce a simple computing model, the *finite automata*,
and characterize the languages that can be decided by these machines, the
*regular languages*.
Then we study the more powerful *pushdown automata* and their corresponding
languages, the *context-free languages*.
Finally, we will discuss *Turing machines*, the most powerful machine model.
But we will also see the limitations of this model; not all problems
can be solved by a Turing machine.
At the end, we will discuss efficiency of Turing machines, mainly in the forrm of
lower bounds, i.e., the theory of NP-completeness.

## 1. Finite automata and regular languages

We will introduce a simple machine model, the *finite automaton (FA)*,
and study its computational power.
We will show that deterministic and non-deterministic FA can decide
exactly the same class of languages, the *regular languages*.
Regular languages are closed under all set operations.
We will learn algorithms to transform a non-determinisitcd FA into a deterministic FA,
to minimize the size of a deterministic FA, and to construct the regular language corresponding
to a FA (and vice versa).
We will also learn powerful methods to prove non-regularity of a language,
for example, the Pumping Lemma.

## 2. Pushdown automata and context-free languages

A *pushdown automaton (PDA)* is a FA with an additional stack to store information.
Non-deterministic PDAs can decide *context-free languages (CFL)*, i.e.,
languages that can be described by a context-free grammar (CFG).
CFL are only closed under some set operations.
While most problems for FA are computable, some problems for CFG are undecidable.
We will see that we can parse context-free languages efficiently.
We will also learn powerful methods to prove non-context-freeness of a language,
for example, the Pumping Lemma.

## 3. Turing machines

A *Turing machine (TM)* is a FA with a memory tape.
It is the most powerful machine model known, but still there are problems that cannot
be decided by a TM, for example the Halting Problem.
We will learn Rice's Theorem, a powerful tool to prove undecidability.
There are many equivalent definitions of languages decidable by TMs,
for example general grammars, Post correspondence systems, lambda calculus, etc.

## 4. Complexity theory

In complexity theory we are interested in classifying languages according to the efficiency of deciding them. P (polynomial time) and NP (non-deterministic polynomial time) are the most prominent classes, and we will study complete problems (the most difficult problems in a class) for NP and PSPACE. We will also shortly mention the concept of Kolmogorov complexity which classifies languages according to the size of their most succinct representation.

# Textbook

This course will closely follow the textbook
*Introduction to the Theory of Computation*
by Michael Sipser, 2nd edition (English), China Machine Press, 2002.
It is mandatory that you have a copy of that book.

In class, I may sometimes teach material that is not in the textbook. I may also skip some material in the textbook. For the exams, however, I expect that you are familiar with everything we did in class, everything covered by the textbook (except some parts that will be explicitly excluded), and everything that appeared in the homework assignments.

Usually, I will not provide any notes in addition to what you find in the textbook. Below, I will provide links to some nice resources when we encounter them.

FOLDOC | On-Line Dictionary of Computing |

DADS | Dictionary of Algorithms and Data Structures |

Introduction | Slides from first class on Mar 4 |

History of computing | Slides from Mar 4 |

The infinity paradox | Discussed on Mar 4 |

Stephen Cole Kleene | History of the Kleene star, Mar 11 |

Kara the ladybug | A programmable finite automaton (see also the original version at ETH and the download page for different Java versions); choose JavaKara on the main menu |

Exorciser | An exercise tool for finite automata (see also the original version at ETH) |

Pattern matching with DFA | Explanations and visualizations |

Pitfalls of the Pumping Lemma | Not my notes |

State minimization | My own notes |

History of automata | Slides from April 2 |

DFAs and PDAs | Highlights |

Alternative models of computing | Lambda Calculus and Billiard ball computer |

Conway's Game of Life | Game of Life, collection of Game of Life links, Jason's Life Page, and a Turing machine implemented in Game of Life |

self.c | A self-replicating C program. |

chaos.c | A chaotic self-printing C program. |