Theory of Computation

Spring 2026

Tuesday 1:30–2:45 p.m.
Thursday 1:30–2:45 p.m.

Sanders Physics 105

Professor Gordon

↓ Current
Part 1: Regular languages Tuesday Thursday

Models of computation

Jan. 22

Theory of computation

Finite automata

Jan. 27

Languages and automata

Jan. 29

Deterministic finite automata

Nondeterminism

Feb. 3

Nondeterministic finite automata

Feb. 5

Relating DFAs and NFAs

Models of the regular languages

Feb. 10

Properties of regular languages

Feb. 12

Regular expressions

Regular and nonregular languages

Feb. 17

The limits of regular languages

Feb. 19

Nonregular languages

End of Part 1

Feb. 24

Review

Feb. 26

Exam 1
Part 2: Context-free languages

Context-free grammars

  • Read § 2.1
  • Assignment 5

Mar. 3

Context-free grammars

Mar. 5

Context-free grammars and context-free languages

Spring break

Mar. 10

🐥

Mar. 12

🐝

Spring break

Mar. 17

🌧

Mar. 19

🌱

Pushdown automata

  • Read § 2.2
  • Assignment 6

Mar. 24

Pushdown automata

Mar. 26

The power of PDAs

Context-free and non-context-free languages

  • Read § 2.2
  • Read Pumping Lemma handout
  • Read Hopcroft et al. (2006) § 7.1 and § 7.4.4
  • Assignment 7

Mar. 31

The limits of context-free languages

Apr. 2

Parsing with CFGs

End of Part 2

Apr. 7

Review

Apr. 9

Exam 2
Part 3: Beyond context-free

Turing machines

  • Read § 3.1–3.2
  • Assignment 8

Apr. 14

Turing machines

Apr. 16

Designing Turing machines

Decidable languages

  • Read § 3.3
  • Read § 4.1
  • Assignment 9

Apr. 21

Turing machines and computation

Apr. 23

At the foot of the mountains of undecidability

The limits of computation

  • Read § 4.2
  • Read § 5.1–5.3
  • Read reductions handout
  • Assignment 10

Apr. 28

The limits of computation

Apr. 30

Reductions and computability

End of Part 3

May 5

The big picture

May 7

📚

May 12

📚

Exam 3

Wednesday, 13 May
9:00–11:00 a.m.

(Optional) review to be scheduled during study week

Present-day computers are built of transistors and wires, but they could just as well be built, according to the same principles, from valves and water pipes, or from sticks and string. The principles are the essence of what makes a computer compute. One of the most remarkable things about computers is that their essential nature transcends technology.

W. Daniel Hillis, The Pattern on the Stone, 1998