CS 4170 Theory of Automata (4) 2005
Catalog Description
Formal models of automata, language, and computability and their relationships. Finite automata and regular languages. Push-down automata and context-free languages. Turing machines, recursive functions, algorithms and decidability. Prerequisites: MATH 2101, MATH 2150, MATH 2304 CROSS-LISTED: MATH 4170
Course Outline:
- Basic notation, preliminaries
Proofs; induction (if necessary)
Strings and alphabets
Algorithms - Regular languages
Regular expressions: definition and use
Finite automata: deterministic, nondeterministic
Non-regular languages; pumping lemma - Context-free languages Grammars, parse trees, derivations, ambiguity
Push-down automata: definition and use
Properties of context-free languages
Non-context-free languages - Recursive and Recursively Enumerable Languages
Turing machines: definition and use, examples Variations on Turing machines
Church's Thesis: computability and algorithms
Grammars: context-sensitive, unrestricted Halting Problem - Chomsky Hierarchy and Applications
Regular, Context-free, and Turing machine languages
Recursive vs. Recursively enumerable
Undecidable problems
Note: Above cannot be covered thoroughly in one quarter; instructor may skim in some areas or omit some sections and/or certain proofs. Students need experience doing formal proofs.
Recommended Texts
- Sipser, Introduction to the Theory of Computation
- Floyd and Beigel, The Language of Machines
- Lewis and Papadimitriou, Elements of the Theory of Computation
- Hopcroft and Ullman, Intro. to Automata Theory, Languages, and Computation
- Cohen, Introduction to Computer Theory
- Kozen, Automata and Computability, Springer