CS4410/7410 THEORY OF COMPUTATION


Overview:    An introduction to the fundamental mathematical models of computation, including both the inherent capabilities and limitations of various computational models as well as their relationships with formal languages.

Textbook:    Sipser
    Introduction to the Theory of Computation
    PWS publishing, 1997

        
Prerequisites:    CS 126 and Math 226

Topics:    1. Introduction                         (1 week)
    2. Finite state automata and regular languages             (3 week)
    3. Deterministic and nondeterministic computations        (2 weeks)
    4. Context-free grammars, languages, and pushdown-automata    (3 weeks)
    5. Turing machines                        (2 weeks)
    6. Undecidable problems                    (2 weeks)
    7. Computational complexity, NP-completeness            (2 weeks)

Prepared by:    Yi Shang

Date:    September 2004

  An introductory study of computation and formal
languages by means of automata and related
grammars. The theory and applications of finite
automata, regular expressions, contextfree
grammars, pushdown automata and Turing
machines are examined. Prerequisite: CS 3270
and MATH 2320.