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:

1. Basic notation, preliminaries
   Proofs; induction (if necessary)
   Strings and alphabets
   Algorithms
2. Regular languages
   Regular expressions: definition and use
   Finite automata: deterministic, nondeterministic
   Non-regular languages; pumping lemma
3. Context-free languages Grammars, parse trees, derivations, ambiguity
   Push-down automata: definition and use
   Properties of context-free languages
   Non-context-free languages
4. 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
5. 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