Theory of Computation

Fall 2022

Tuesday 12:00–1:15 p.m.
Thursday 12:00–1:15 p.m.
Sanders Physics 105

Professor Gordon

Tuesday Thursday

1

Models of computation

Aug. 30

Class 1

Theory of computation

Sep. 1

Class 2

Finite automata

2

Finite automata

Sep. 6

Class 3

Deterministic finite automata

Sep. 8

Class 4

Nondeterministic finite automata

3

Regular languages and automata

Sep. 13

Class 5

Relating DFAs and NFAs

Sep. 15

Class 6

Properties of regular languages

4

Regular and non-regular languages

Sep. 20

Class 7

Regular expressions

Sep. 22

Class 8

The limits of regular languages

5

Exam 1

Sep. 27

Review

Exam 1 review

Sep. 29

Exam

Exam 1

6

Context-free grammars

Oct. 4

Class 9

Context-free grammars

Oct. 6

Class 10

Context-free grammars and context-free languages

7

Pushdown automata

  • Read  § 2.2
  • Assignment 6

Oct. 11

Class 11

Pushdown automata

Oct. 13

Class 12

The power of PDAs

8

October Break

  • Extra-credit assignment 1

Oct. 18

No class

🍁

Oct. 20

No class

🍂

9

Context-free and non-context-free languages

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

Oct. 25

Class 13

The limits of context-free languages

Oct. 27

Class 14

Parsing with CFGs

10

Exam 2

Nov. 1

Review

Exam 2 review

Nov. 3

Exam

Exam 2

11

Turing machines

  • Read § 3.1–3.2
  • Assignment 8

Nov. 8

Class 15

Turing machines

Nov. 10

Class 16

Designing Turing machines

12

Decidable languages

  • Read § 3.3
  • Read § 4.1
  • Assignment 9

Nov. 15

Class 17

Turing machines and computation

Nov. 17

Class 18

At the foot of the mountains of undecidability

13

The limits of computation

  • Read § 4.2
  • Extra-credit assignment 2

Nov. 22

Class 19

The limits of computation

Nov. 24

No class

🥧

14

Computability

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

Nov. 29

Class 20

Computability and reductions

Dec. 1

Class 21

The big picture

15

Review

Dec. 6

Review

Exam 3 review

Dec. 8

No class

📚

16

Final exams

Dec. 13

Exam

Exam 3
9:00–11:00 a.m.

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