Date: Wed, 20 Nov 1996 22:24:53 GMT
Server: NCSA/1.5
Content-type: text/html
Last-modified: Mon, 11 Nov 1996 15:20:21 GMT
Content-length: 6694
CS121: Introduction to Formal Systems and Computation
CS121: Introduction to Formal Systems and Computation
Computer Science 121 is an undergraduate course introducing
automata, formal languages, computability, uncomputability,
computational complexity, and NP-completeness. The theme of the course is
reasoning about formal systems.
This page provides access to on-line course materials.
Table of Contents
General Information:
Announcements:
Problem Sets:
Problem set policies can be found here.
- Problem Set 0:
Induction Relations, etc. Optional but recommended.
Distributed: Tuesday, September 17.
- Problem Set 1:
Regular expressions, Finite automata, and Algorithms.
Distributed: Tuesday, September 24.
- Problem Set 2:
Equivalence of regular expressions, finite automata; Closure properties.
Distributed: Tuesday, October 1.
- Problem Set 3:
Non-regular languages, Pumping theorems, Automata minimization.
Distributed: Tuesday, October 8. Revised: Thursday,
October 10.
- Problem Set 4:
Context free grammars, Pushdown automata.
Distributed: Tuesday, October 22.
- Problem Set 5:
Closure Properties, Pumping Theorem, DPDAs, Parsing.
Distributed: Tuesday, October 29.
- Problem Set 6:
Top down parsing, intro to Turing Machines.
Distributed: Tuesday, November 5.
Errata in text:
Please send any errors that you find in the text, and any proposed fixes to
the errors to
cs121@deas.harvard.edu.
The official fixes for the text are archived
here.
cs121@deas.harvard.edu