22C:135 Introduction to Computation Theory

Instructor: Arthur C. Fleck

Teaching Assistant: Jin Zhou, Office: B20J MLH, Hours: 11-12:20 T-Th, Ph.: 335-3650

Time/place: 10:30 am MWF / 110 MLH

Text: A. C. Fleck, Formal Models of Computation:
The Ultimate Limits of Computing, at IMU bookstore

General background from the formal prerequisite 22C:34 will be assumed. In particular, it will be assumed that the student has basic knowledge of sets, functions, relations, and graphs, plus experience with formal proofs, especially induction proofs.

The course will involve two in-class exams, announced well in advance, and a final exam, scheduled for Monday December 16 from 2:15-4:15 pm in our regular classroom. There is also weekly homework. The assignments in the course do not involve computer programming. The work involves problem solving, and the careful proof of the conclusions that can be drawn from rigorous definitions of the computing models.

Anyone who has a disability that requires modification of testing or other class arrangements should contact me as soon as possible. Please see me after class or during office hours.

- Finite state models
- regular expressions
- deterministic vs. non-deterministic automata
- regularity preserving operations
- pumping lemma and non-regular languages
- transducers and state minimizations

- Grammars and the Chomsky hierarchy
- context-free grammars and languages
- derivations, derivation trees, and ambiguity
- operations preserving context-free languages
- normal form grammars and parsing
- pushdown automata
- pumping lemma and non context-free languages

- context-sensitive grammars and languages
- derivations as computations
- leftmost limitations and loss of the derivation tree concept
- linear bounded automata
- operations preserving context-sensitive languages, and erasing problems

- context-free grammars and languages
- Turing machines and uncomputability
- relation to general phrase structure grammars
- recursive functions
- random access machine (RAM) simulation
- universal Turing machine
- undecidability (e.g., halting problem, Post's correspondence problem, context-free ambiguity)

Related Web sources:

- Fall '02 score summary
- visuals, part I (corrected)
- Sample Exam I (PDF)
- visuals, part II
- Sample Exam II (PDF)
- visuals, part III
- non context-free grammar examples (PDF)
- decision problem summary (PDF)
- sample final exam (PDF)
- Alan Turing homepage
- Finite-state software tools
- Links to more finite-state software tools
- Turing machine simulator
- Graphical Turing machine simulator for Windows
- FLAP - automata simulation package