CIS 511, Fall 2021
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, undecidability,
and basics of recursive function
theory;

(3)
Complexity theory.
This semester, we will put more emphasis on (2) and (3).
In particular, for (3), we will cover
the classes P and NP, NPcomplete problems, coNP, Pspace,
Pspacecomplete problems.
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 (topdown and bottomup 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
 Chapter 1
 Chapter 2
 () Basics of language theory: alphabets, strings, concatenation,
languages, operations on languages (including Kleene *)
 Chapter 3
 () Deterministic finite automata (DFA's)
 The crossproduct construction
 Maps (morphisms) of DFA's
 () Nondeterministic finite automata (NFA's)
 epsilonclosure
 From NFA's to DFA's, the subset algorithm (Rabin and Scott)
 Finite state automata with output; transducers

Chapter 4 (*)
 Definition of a Hidden Markov Model (HMM)
 The Viterbi algorithm and the forward algorithm

Chapter 6
 Rightinvariant equivalence relations
 Finding minimal DFA's
 State equivalence, minimal DFA's
 The pumping lemma for regular languages
 A fast algorithm for checking state equivalence
The following topics will most likely be omitted.
 (*) 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
 () Contextfree grammars and contextfree languages
 () Leftmost derivations, rightmost derivations, parse trees
 The universality of leftmost derivations
 () Cleaningup contextfree grammars (erules, chain rules)
 () Chomsky Normal Form
 () Rightlinear grammars and regular languages
 (*) A glimpse at LRparsing
PART II: Models of Computation, Undecidability,
Basics of Recursive Function Theory

Chapter 1
 () Generalities on computability, Partial Functions
 RAM programs (Post machines)
 Turing Machines
 Equivalence of RAM programs and Turing machines
 Listable kanguages and computable languages
 A simple function not known to be computable
 The Primitive recursive functions
 Primitive Recursive Predicates
 The Partial computable functions

Chapter 2
 Pairing Functions
 Equivalence of Alphabets
 Coding of RAM programs
 Unsolvability of the Halting Problem
 Universal RAM programs
 Indexing of RAM programs
 Kleenee's Tpredicate
 A noncomputable function: busy beavers

Chapter 3
 Acceptable Indexings
 Undecidable Problems
 Reducibility and Rice's Theorem
 Listable (recursively enumerable) Sets
 Reducibility and Complete Sets (w.r.t. ManyOne reducibility)
 Chapter 4
 Syntax of the lambdacalculus
 betareduction and betaconversion; the ChurchRosser theorem
 Some useful combinators
 Representing the natural numbers
 Fixed point combinators and recursively defined functions
 lambdadefinability of the computable functions
 Definability of functions in typed lambdacalculi
 head normal forms and the partial computable functions

Chapter 5 (*)
 (*) The Recursion Theorem, versions 1, 2, 3
 (*) The Extended Rice Theorem
 (*) Creative and productive sets; incompleteness

Chapter 6
 Diophantine equations; Hilbert's tenth problem
 Diophantine sets and listable sets
 Some applications of the DPRM theorem
 Godel's incompleteness theoeem

Chapter 7
 The Post correspondence problem
 (*) Some undecidable results for CFG's
 (*) More undecidable properties of Languages
 (*) Undecidability of validity in firstorder logic
PART III: Computational Complexity

Chapter 8
 The class P
 Directed graphs, Paths
 Eulerian cycles
 Hamiltonian cycles
 Propositional logic and satisfiability
 The class NP, NPcompleteness
 The bounded tiling problem is NPcomplete
 The Cook Levin Theorem
 Satisfiability of arbitrary propositions and CNF

Chapter 9
 Statement of the problems
 Proofs of NPcompleteness
 Succint certificates, coNP, and EXP

Chapter 10 (*)
 Prime numbers and composite numbers
 Methods for primality testing
 Modular arithmetic, the groups Z/nZ, (Z/nZ)*
 The Lucas theorem
 Lucas trees
 Algorithms for computing powers modulo m
 PRIMES is in in NP

Chapter 11
 The class PS (PSPACE) and NPS
 Savitch's theorem: PS = NPS
 A complete problem in PS: QBF
 (*) Provability in intuitionistic propositional logic
Back to
Gallier Homepage
published by: