CIS 511, Summer 1, 2006

Introduction to the Theory of Computation Course Information May 15

Coordinates:

Instructor:

Office Hours:

Teaching Assistants:

Office Hours:

Newsgroup:

Textbook (required):

Also recommended:

Introduction to the Theory of Computation, Michael Sipser, PWS Publishing

Additional Useful References:

Automata and Computability, Dexter Kozen, Springer

Theory of Computation, Derick Wood, Wiley

Mathematical Theory of Computation, Zohar Manna, McGraw Hill

An Introduction to the General Theory of Algorithms, M. Machtey and P. Young, Elsevier North-Holland

Introduction to Formal Language Theory, M. Harrison, Addison Wesley

The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Martin Davis, Raven Press

Theory of Recursive Functions and Effective Computability, Hartley Rogers, MIT Press

Introduction to Metamathematics, Stephen Kleene, North-Holland

Computability and Unsolvability, Martin Davis, McGraw-Hill

Enumerability, Decidability, Computability, Hans Hermes, Springer-Verlag

Computational Complexity, Christos Papadimitriou, Addison Wesley

Some Historical and Leading Figures

Recent Paper Relevant to the Course Material

Grades: homework assignments (100%),

Homework assignments (4 of them)

• Latex macros, "mac.tex"
• Latex macros, "mathmac.tex"
• Homework 1 ps   |  pdf   |  (Latex file)
• Homework 2 ps   |  pdf   |  (Latex file)
• Homework 3 ps   |  pdf   |  (Latex file)
• Homework 4 ps   |  pdf   |  (Latex file)

  A Word of Advice :

  Expect to be held to high standards, and conversely! In addition to transparencies, I will distribute lecture notes. Please, read the course notes regularly, and start working early on the problems sets. They will be hard! Take pride in your work. Be clear, rigorous, neat, and concise. Preferably, use a good text processor, such as LATEX, to write up your solutions.

  Due to the difficulty of the homework problems and in order to give you an opportunity to learn how to collaborate more effectively (I do not mean "copy"), I will allow you, in fact, URGE you, to work in small groups. A group consists of AT MOST THREE students. All members of a group will get the SAME grade on the homeworks and the project.

  We will have special problems sessions, roughly every two weeks, during which we will solve the problems together. I am hard to convince, especially if your use blatantly ``handwaving'' arguments.

  Late Homework Policy

  If Homework due on Tuesday:
  • If turned in on Wednesday, 10% off
    
  • If turned in on Thursday, 40% off

  If Homework due on Thursday:

  • If turned in on Friday, 10% off
    
  • If turned in on Monday, 50% off

  ** ZERO credit ** if turned in later than specified above!
  Policy will be ** strictly enforced **
  No Excuses, plan ahead!

  Plagiarism Policy

  I assume that you are all responsible adults.
  Copying old solutions verbatim or blatantly isomorphic solutions are easily detectable.
  DO NOT copy solutions from old solution sheets, books, or friend!
  Either credit will be split among the perpetrators, or worse!

  Brief description:

  The course provides an introduction to the theory of computation. The treatment is mathematical, but the point of view is that of Computer Science. Roughly speaking, the theory of computation consists of three overlapping subareas: (1) formal languages and automata; (2) Models of computation, computability, and basics of recursive function theory; (3) complexity theory.

  Level of the course: Students are expected to have undergraduate knowledge of the theory of computation, roughly equivalent to the material covered in CSE262. Most material on the regular languages will not be covered in class.
  Material assumed to be known and either not covered in class or reviewed very quickly is marked with a (-).

  The course will focus mostly on (1) and (2), but will also cover some of (3): the classes P and NP, and NP-complete problems. Applications of (1) to programming (and natural) language specification and parsing (top-down and bottom-up parsing) will be mentioned, whenever appropriate.
  

  Topics will include:

  PART 1: Languages and Automata
  

  • (-) Basics of language theory: alphabets, strings, concatenation, languages, operations on languages (including Kleene *)
  • (-) Deterministic finite automata (DFA's)
  • The cross-product construction
  • Maps and morphisms of DFA's
  • (-) Nondeterministic finite automata (NFA's)
  • (-) From NFA's to DFA's, the subset algorithm (Rabin and Scott)
  • (-) Labeled directed graphs, NFA's and DFA's
  • (-) Regular languages and regular expressions
  • (-) From regular expressions to NFA's
  • (-) From NFA's to regular expressions (node elimination)
  • Right-invariant equivalence relations
  • The Nerode/Myhill characterization theorem
  • The pumping lemma for regular languages
  • State equivalence, minimal DFA's
  • (-) Context-free grammars and context-free languages
  • (-) Leftmost derivations, rightmost derivations, parse trees
  • The universality of leftmost derivations
  • (-) Cleaning-up context-free grammars (e-rules, chain rules)
  • (-) Chomsky Normal Form
  • (-) Right-linear grammars and regular languages
  • Eliminating useless productions
  • Context-free languages as fixed points
  • Greibach Normal Form
  • Tree domains, Gorn trees, and parse trees
  • A strong pumping lemma for context-free languages: Ogden's lemma
  • (-) Pushdown Automata (PDA's), instantaneous descriptions, acceptance modes
  • DPDA's (Deterministic PDA's)
  • From context-free grammars to PDA's
  • From PDA's to context-free grammars
  • A glimpse at LR-parsing

  PART II: Models of Computation and Basics of Recursive Function Theory

  • Generalities on computability, Partial Functions
  • RAM programs (Post machines)
  • Turing Machines
  • RAM computable functions are Turing computable
  • Turing computable functions are RAM computable
  • Primitive recursive functions
  • Recursive and partial recursive functions
  • The equivalence of Turing computable functions and partial recursive functions
  • Recursively enumerable languages and recursive languages
  • Pairing Functions
  • Coding of RAM programs
  • Unsolvability of the Halting Problem
  • A universal RAM program
  • The Enumeration Theorem
  • (*) Kleenee's T-predicate
  • (*) Kleene Normal Form Theorem
  • Acceptable Indexings
  • (*) The s-m-n Theorem
  • Undecidable Problems
  • K and TOTAL are not recursive
  • Rice's Theorem for Recursive Sets
  • Recursively Enumerable Sets
  • Many-One reducibility
  • Complete Sets (w.r.t. Many-One reducibility)
  • TOTAL is not re
  • (*) TOTAL, FINITE, and their complements, are not re
  • (*) The Recursion Theorem, versions 1, 2, 3
  • (*) The Extended Rice Theorem
  • (*) Productive and Creative Sets
  • The undecidability of Post's correspondence problem
  • Undecidable Properties of CFL's; Greibach's Theorem and applications

  PART III: Computational Complexity

  • The class P
  • Examples of Problems
  • Boolean Satisfiability
  • The class NP
  • Polynomial-time reductions
  • NP-completeness
  • Cook's Theorem

  Some Course Notes and Slides

  • Discrete math. basics, induction, inductive definitions
    (Chapter from ``Logic for Computer Science'', by J. Gallier)   (ps)   |  (pdf)
  • Discrete mathematics for computer science
    (Book in progress, by J. Gallier)   (html)  
  • Generalities, Motivations, Basics of language theory, DFA's, the cross-product construction, morphisms and maps of DFA's, NFA's   (ps)   |  (pdf)
  • NFA's, the subset construction, transducers, labeled directed graphs, regular expressions (slides)   (ps)   |  (pdf)
  • Notes on the closure definition of the regular languages (notes)   (ps)   |  (pdf)
  • The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (slides)   (ps)   |  (pdf)
  • The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (notes)   (ps)   |  (pdf)
  • Context-free grammars and context-free languages (slides)   (ps)   |  (pdf)
  • BNF convbnf
  • BNF metabnf
  • BNF pasbnf
  • BNF toybnf
  • Context-free languages as fixed points, Greibach normal form (slides)   (ps)   |  (pdf)
  • Parse Trees, and Ogden's Lemma (slides)   (ps)   |  (pdf)
  • Context-free grammars, context-free languages, parse trees, and Ogden's Lemma (notes)   (ps)   |  (pdf)
  • Pushdown Automata and context-free languages (slides)   (ps)   |  (pdf)
  • LR-parsing and shift/reduce algorithm (slides)   (ps)   |  (pdf)
  • A survey of LR-parsing methods. The graph methods for computing FIRST, FOLLOW, and LALR(1) Lookahead sets (notes)   (ps)   |  (pdf)
  • RAM programs (Post machines), Turing Machines (slides, ps)
  • Primitive recursive functions, partial recursive functions (slides, ps)
  • RAM programs (Post machines), Turing Machines, Primitive recursive functions, partial recursive functions (slides, pdf)
  • Coding of RAM programs, Unsolvability of the Halting Problem, A universal RAM program, The Enumeration Theorem, Kleene's T-predicate, Kleene Normal Form Theorem (slides, ps)   |  (slides, pdf)
  • Elementary Recursive Function Theory, Acceptable indexings, the s-m-n Theorem, Undecidable Problems, K and TOTAL are not recursive, Rice's Theorem (slides, ps)   |  (slides, pdf)
  • Recursively Enumerable Sets, Many-One Reducibility, Complete Sets, TOTAL, FINITE, and their complements, are not r.e. (slides, ps)   |  (slides, pdf)
  • The Recursion Theorem, the Extended Rice Theorem, Productive and Creative Sets (slides, ps)   |  (slides, pdf)
  • The Post Correspondence Problem (PCP), Undecidable properties of languages, Greibach's theorem (printed slides, pdf)   |  (slides, pdf)
  • Computational Complexity, the class P, satisfiability, the class NP, NP-completeness, Cook's theorem (printed slides, pdf)   |  (slides, pdf)
  • Eulerian and Hamiltonian cycles (slides, ps)   |  (slides, pdf)
  • Prove that P = NP, and get a one million dollar reward! (Clay Institute)
  • Phrase structure grammars, context-sensitive grammars (printed slides, pdf)
  • Computability, Undecidability, and Basic Recursive Function Theory (notes) (ps)   |  (pdf)
  • Theory of Computation in German! (slides)
  • Book Manuscript, by Gallier and Hicks

  Relevant Fun Software

  Jflap

  ---

  Back to Gallier Homepage

  published by:

  Jean Gallier