Computation Theory
Spring 2005 Semester

All mornings at 9:00   :)

Basic Information

Instructor
Name: Andrea Valente
Email: av@cs.aue.auc.dk
Office
Room: FUV 2.49
Phone: 7912 7720
Classes
Classroom: B202
Time slot: Monday morining / Wednesday morning

Course structure

This course consists of approximately 15 classes, each of which is divided into a lecture period followed by a laboratory period. The lecture period for each class will, on average, consist of two 45 minute lecture sessions, with a short break in between.

Each class will have an associated reading assignment. Students are expected to keep up with assigned readings as the course progresses.

Course materials

Each student should obtain the following materials:

Reading suggestions

Course examination

Details concerning the course exam will be provided later.

Schedule

week date time class topics readings
6
mon. 1 introduction, history, background material ETOC: 1.1-1.3
7
mon. 2 background material ETOC: 1.4-1.6
8 mon. 3 background material, alphabets ETOC: 1.7-1.8
9 mon. 4 deterministic finite automata ETOC: 2.1
10 mon. 5 nondeterministic finite automata, FAs, and regular expressions ETOC: 2.2-2.3
11 mon. 6 regular languages, nonregular languages [*] ETOC: 2.3-2.4
12 mon. 7 context free grammars, pushdown automata [x] ETOC: 3.1, and 3.3
13

Easter

13 wed. 8 PDAs and CFGs, CF languages, non-CF languages ETOC: 3.4, 3.5, and 3.7
14 mon. 9 Turing Machines ETOC: 4.1
14 wed. 10 programs for Turing machines, extending Turing machines ETOC: 4.2-4.3

while language & MU
15 mon. 11 random access TMs, nondeterministic TMs ETOC: 4.4 - 4.5
15 wed. 12 undecidability [xx] ETOC: 5.1, 5.2 , 5.3, and 5.4
16 mon. 13 the class P ETOC: 6.1-6.2
16 wed. 14 boolean satisfiability, the class NP ETOC: 6.3-6.4
17 mon. 15 NP-completeness ETOC: 7.1-7.4

About the pumping lemma for regular languages:

Few extra exercises about CF and non-CF languages:

Example of undecidable problems (implemented in javascript):