Syllabus for CSC 4170-50
Theory of Computation

Spring 1996
Tuesday-Thursday, 6:00 p.m. -- 7:15 p.m.
Mendel 258

Instructor: David Matuszek, dave@vfl.paramax.com

These pages are best viewed using Netscape Navigator 2.0. Mosaic has a bug that prevents links within the table from working; earlier versions of Netscape do not support subscripts and superscripts. You can download Netscape Navigator 2.0 by clicking the following button:

Netscape now!

Email is by far the best way to contact me. During the workday I can usually respond almost immediately--if I don't, I'm probably tied up in a meeting. I don't usually check email in the evenings, and only occasionally on weekends.

Textbook: An Introduction to Formal Languages and Automata
Peter Linz, ISBN 0-669-17342-8

Here are some comparable courses I've found on the Web:

Links to other relevant pages will be found in the appropriate lessons.

Grades will be based primarily on exams. I expect to grade 20% homework, 30% midterm, and 50% final exam. (The final exam will be comprehensive.) These numbers may be modified slightly depending on the amount of homework I assign.

Here are the topics we will cover and the relevant chapters in the book. Dates are tentative.

Date Chapter Topic
Jan 16 1.1 Introduction and review
Jan 18 ---- BNF
Jan 23 1.2 Languages and grammars (most important!)
Jan 25 2.1 DFAs and their implementation
Jan 30 2.2 NDFAs and their implementation
Feb 1 2.3 DFAs = NDFAs
Feb 6 3.1 Regular expressions
Feb 8 3.2 Regular expressions denote regular languages
Feb 13 3.3 Regular grammars
Feb 15 4.1, 4.2 Closure, homomorphism
Feb 20 4.3 Pigeonhole principle, pumping lemma (difficult)
Feb 22 ---- Review for midterm
Feb 27 ---- Midterm exam
Feb 29 5.1 CFGs
Mar 5 5.2 Parsing and ambiguity
Mar 7 7.1 Pushdown automata
Mar 19 7.2, 7.3 NPDAs & CFGs
Mar 21 8.1 A pumping lemma for cfgs (still difficult)
Mar 26 9.1 Turing machines
Mar 28 10.4, 10.5 Universal Turing Machines and LBAs
Apr 2 11.1 Recursively enumerable languages
Apr 9 11.2 Unrestricted grammars
Apr 11 11.3, 11.4 The Chomsky hierarchy
Apr 16 12.1 Undecidable problems
Apr 18 13.1 Church's Thesis
Apr 23 13.2 Complexity Theory, P and NP
Apr 25 all Review for Final
Apr 30 ---- Go over homework, Q & A
May 7 Cumulative Final exam 5:30-7:30


Copyright 1996 by David Matuszek
Last modified Apr 23, 1996