4 Course Content and Outline

The official kursplan is available on this link. A more offering-specific outline is shown below.

The numbers shown in rectangular brackets (i.e., [..]) identify chapters and sections in the textbook. The items in rectangular brackets which begin with “X” indicate special topics not covered in the textbook. These topics are described in Section 5.2.

The numbers in angle brackets ⟨..⟩ indicate the approximate number of 45-minute lecture periods which will be devoted to the topic. This number is approximate, and in particular is rounded to the nearest integer. Adjustments will be made as the course progresses, and so the table below should not be used a definitive guide to which topics will be covered on which days.

I

Introduction [1] ⟨2⟩

FA

Finite Models of Computation

FA.1

Finite Automata [2] ⟨2⟩

FA.2

Regular Languages and Grammars [3] ⟨2⟩

FA.3

Closure and Membership for Regular Languages [4] ⟨2⟩

FA.4

Tools and Applications [XFA1-XFA3] ⟨1⟩

CF

Stack-Based Models of Computation

CF.1

Context-Free Languages and Grammars [5] ⟨2⟩

CF.2

Simplification and Normalization [6] ⟨2⟩

CF.3

Acceptors for Context-Free Languages [7] ⟨2⟩

CF.4

Closure and Membership for Context-Free Languages [8] ⟨2⟩

CF.5

Tools and Applications [XCF1-XCF4] ⟨2⟩

GC

General Models of Computation

GC.1

Turing Machines and Turing’s Thesis [9,10.3] ⟨2⟩

GC.2

The Programming Model of Computation [XCT1] ⟨1⟩

GC.3

The Universal Computer [10.4] ⟨1⟩

GC.4

The Classical Language Hierarchies [11] ⟨1⟩

GC.5

The Limits of Algorithmic Computation [12,XCT2] ⟨2⟩

CC

Computational Complexity [14] ⟨2⟩

R

Review ⟨2⟩