CIS 511, Spring 2013
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.
This semester (and Spring semester), we will put more emphasis on (2) and (3).
In particular, for (3), we will cover
the classes P and NP, NP-complete problems, co-NP,
and public key cryptography and RSA.
In order to cover more material from (2) and (3), the
order in which the material will be presented has been changed
from previous years.
Applications
of (1) to programming (and natural) language specification and
parsing (top-down and bottom-up parsing) will be mentioned,
whenever appropriate.
Students are expected to have some undergraduate knowledge of the
theory of computation. Some material assumed to be known
will either not be covered in class or reviewed quickly. This material is marked
with a (-).
Syllabus:
Topics will include: ((*) means: if time permits)
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
- (-) Nondeterministic finite automata (NFA's)
- From NFA's to DFA's, the subset algorithm (Rabin and Scott)
- (*) An Application of NFA's: Text Search
- (-) Regular languages and regular expressions
- (-) From regular expressions to NFA's
- (-) From NFA's to regular expressions (node elimination)
- Closure properties of the regular languages
- (*) Applications of regular expressions: Lexical analysis, finding patterns
in text
- 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
- Tree domains, Gorn trees, and parse trees
- A strong pumping lemma for context-free languages: Ogden's lemma
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
- The undecidability of Post's correspondence problem
- Undecidable Properties of CFL's; Greibach's Theorem and applications
- (*) Undecidability of Hilbert's tenth problem (Solvability of Diophantine
Equations)
- (*) Diophantine sets = recursively enumerable sets
- (*) Diophantine definabiliy of the primes
PART III: Computational Complexity
- The class P
- Examples of Problems
- Boolean Satisfiability
- The class NP
- Polynomial-time reductions
- NP-completeness
- Cook's Theorem
- The class co-NP
- Public Key Cryptography (RSA)
- (*) The classes PS and NPS
- (*) Savitch's Theorem: PS = NPS
- (*) The QBF Problem
- (*) QBF is PS-complete
- (*) Randomized Turing Machines
- (*) The class RP; ``Monte-Carlo Algorithms''
- (*) The class ZPP; ``Las Vegas Algorithms''
- (*) Relationships between RP, ZPP, P and NP
- (*) The complexity of primality testing
- (*) Primality testing and RP
PART IV: More Formal Language and Automata Theory
- (-) Eliminating useless productions
- Greibach Normal Form
- (-) 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
Back to
Gallier Homepage
published by: