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

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 out
Optional LaTeX template

5

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)

4

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

3

Feb. 12

NFAs and regular expressions

Reading: Section 1.3.

Assignment 2 (Solutions)
Optional LaTeX template

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.
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