CMPU 240

Language Theory and Computation

Spring 2019

Tuesday & Thursday, 4:35–5:50 p.m.
Sanders Physics 105

Prof. Jonathan Gordon

Week Tuesday Thursday

16

May 14

📚 Study Period

May 16

📝 Exam Period

Final Exam on May 17, 9 a.m., SP 309

15

May 7

Exam 3 review and practice problems (Solutions)

May 9

📚 Study Period

14

Apr. 30

Reductions

Reading: Section 5.1
Optional Reading: Section 5.2

Assignment 8 (Solutions)

May 2

The Big Picture

Handout on reductions

13

Apr. 23

Decidability

Reading: Section 4.2

Quiz 5 (Solutions)

Assignment 7 (Solutions)

Apr. 25

The Limits of Computation

Optional programming assignment 3

12

Apr. 16

Turing machines, part 2

Reading: Section 3.3

Assignment 6 (Solutions)

Apr. 18

Turing machines, part 3

Reading: Section 4.1

Optional programming assignment 2

11

Apr. 9

Exam 2 (Solutions)

Apr. 11

Turing machines

Reading: Sections 3.1–3.2

Optional programming assignment 1

10

Apr. 2

Closure properties and Pumping Lemma for CFLs

Reading: Section 2.3

Quiz 4 solutions

Apr. 4

Exam 2 review

Exam 2 review and practice problems (Solutions)

Handout: Pumping Lemma examples

9

Mar. 26

Equivalence of CFGs and PDAs

Mar. 28

CFLs and parsing

Reading: Hopcroft et al., 2006: 7.1 (CNF) and 7.4.4 (CYK)

Assignment 5 (Solutions)

8

Mar. 19

🐇 Spring Break

Mar. 21

🐥 Spring Break

7

Mar. 12

🌱 Spring Break

Mar. 14

🌧 Spring Break

6

Mar. 5

CFGs and pushdown automata

Reading: Section 2.2

Mar. 7

Pushdown automata continued

Assignment 4 (Solutions)

5

Feb. 26

Exam 1 review

Exam 1 review and practice problems (Solutions)

Feb. 28

Context-free grammars

Reading: Section 2.1

Exam 1 (Solutions)

4

Feb. 19

The Pumping Lemma and non-regular languages

Reading: Section 1.4

Assignment 3 (Solutions)

Feb. 21

Non-regular languages and closure properties

Quiz 3 solutions

3

Feb. 12

NFAs and regular expressions

Reading: Section 1.3

Assignment 2 (Solutions)

Feb. 14

Regular expressions continued

2

Feb. 5

Regular languages and nondeterministic finite automata

Reading: Section 1.2

Quiz 2 solutions

Assignment 1 (Solutions)

Feb. 7

Relating deterministic and nondeterministic finite automata

1

Jan. 29

Finite automata

Reading: Section 1.1

Quiz 1 solutions

Jan. 31

Finite automata continued

0

Jan. 22

❄️

Jan. 24

Introduction

Handout: Syllabus

Reading: Chapter 0

Tools

Perspectives

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