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:
    I.  Basic notation, preliminaries 
        Proofs; induction (if necessary)
        Strings and alphabets
        Algorithms

   II.  Regular languages 
        Regular expressions: definition and use
        Finite automata: deterministic, nondeterministic
        Non-regular languages; pumping lemma

  III.  Context-free languages 
        Grammars, parse trees, derivations, ambiguity
        Push-down automata: definition and use
        Properties of context-free languages
        Non-context-free languages

   IV.  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

    V.  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