CMPU 240

Language Theory and Computation

Spring 2020

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

Prof. Jonathan Gordon

Tuesday Thursday

1

Models of computation

Jan. 21

Jan. 23

Introduction

2

Finite automata

Jan. 28

Finite automata

Jan. 30

Deterministic finite automata

3

Nondeterminism

Feb. 4

Nondeterministic finite automata

Feb. 6

Relating DFAs and NFAs

4

Regular expressions

Feb. 11

Properties of regular languages

Feb. 13

Regular expressions

5

Regular and non-regular languages

Feb. 18

Regular expressions, regular languages

Feb. 20

The limits of regular languages

6

Context-free grammars

Feb. 25

Exam 1 Review

Feb. 27

Context-free grammars

7

CFGs and parsing

Mar. 3

Designing CFGs

Mar. 5

Parsing with CFGs

8

Mar. 10

Spring Break

Mar. 12

Spring Break

9

Mar. 17

Spring Break

Mar. 19

Spring Break

10

Pushdown automata

Mar. 24

Pushdown automata

Mar. 26

The power of PDAs

11

Context-free and non-context-free languages

Mar. 31

The limits of context-free languages

Apr. 2

Closure properties for CFLs

12

Exam 2

Turing machines

  • Read § 3.1–3.3

Apr. 7

Exam 2 review

Apr. 9

Turing machines

13

Turing machines

Apr. 14

Turing machines, continued

Apr. 16

Turing machines and computation

14

Undecidability

Apr. 21

At the foot of the mountains of undecidability

Apr. 23

Undecidability

15

The limits of computation

Apr. 28

The limits of computation

Apr. 30

The big picture

16

May. 5

Exam 3 review

May. 7

Study Period

17

May 12

Study Period

May 14

Exam Period

18

May 19

Exam Period

Resources

Perspectives

Software

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