CMPU 240

Theory of Computation

Spring 2021

Tuesday & Thursday, 1:30–2:45 p.m.
Sanders Classroom 212 (Spitzer Auditorium) and Zoom

Prof. Jonathan Gordon

Tuesday Thursday

1

Introduction

Feb. 16

Feb. 18

Lecture 1

Theory of computation

2

Finite automata

Feb. 23

Lecture 2

Finite automata

Feb. 25

Lecture 3

Deterministic finite automata

3

Nondeterminism

Mar. 2

Lecture 4

Nondeterministic finite automata

Mar. 4

Lecture 5

Relating DFAs and NFAs

4

Models of the regular languages

Mar. 9

Lecture 6

Properties of the regular languages

Mar. 11

Lecture 7

Regular expressions

5

Regular and non-regular languages

Mar. 16

Lecture 8

The limits of regular languages

Mar. 18

Lecture 9

Proving non-regularity

6

Context-free grammars, part 1

Mar. 23

Exam 1 review

Mar. 25

Lecture 10

Context-free grammars

7

Context-free grammars, part 2

Mar. 30

Lecture 11

Context-free grammars and context-free languages

Apr. 1

No class

8

Pushdown automata

Apr. 6

Lecture 12

Pushdown automata

Apr. 8

Lecture 13

The power of PDAs

9

Context-free and non-context-free languages

Apr. 13

Lecture 14

The limits of context-free languages

Apr. 15

Lecture 15

Closure properties for CFLs

10

Working with context-free languages

Apr. 20

Lecture 16

Parsing with CFGs

Apr. 22

Exam 2 review

11

Turing machines

Apr. 27

Lecture 17

Turing machines

Apr. 29

Lecture 18

Designing Turing machines

12

Turing-decidable languages

May 4

Lecture 19

Turing machines and computation

May 6

Lecture 20

At the foot of the mountains of undecidability

13

The limits of computation

May 11

Lecture 21

The limits of computation

May 13

Lecture 22

Computability and reductions

14

The big picture

May 18

Lecture 23

The big picture

May 20

Exam 3 review

15

May 25

Study Period

May 27

Study Period

Resources

Perspectives

Tools

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