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


Mar. 12

🌱 Spring Break

Mar. 14

🌧 Spring Break


Mar. 5

CFGs and pushdown automata

Reading: Section 2.2

Mar. 7

Pushdown automata continued

Assignment 4 out
Optional LaTeX template


Feb. 26

Exam 1 review

Exam 1 review topics and problems (Solutions to practice problems)

Feb. 28

Context-free grammars

Reading: Section 2.1.

Exam 1 (Solutions)


Feb. 19

The Pumping Lemma and non-regular languages

Reading: Section 1.4.

Assignment 3 (Solutions)
Optional LaTeX template

Feb. 21

Non-regular languages and closure properties

Quiz 3 solutions


Feb. 12

NFAs and regular expressions

Reading: Section 1.3.

Assignment 2 (Solutions)
Optional LaTeX template

Feb. 14

Regular expressions continued


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


Jan. 29

Finite automata

Reading: Section 1.1.

Quiz 1 solutions

Jan. 31

Finite automata continued


Jan. 22


Jan. 24


Handout: Syllabus

Reading: Chapter 0.
Optional reading: How I faced my fears and learned to be good at math

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

Interesting Links