Machines
The general syntax of machines and programs
Acceptors, recognizers, and transducers; determinism
Finite automata, counters, stacks, Turing machines and RAM
Simulation
General concepts of simulation
One control simulates two controls
Unsigned counter (with or without nonzero) = signed counter
Eliminating the empty test from stacks
Standardizing programs
Two counters simulate a stack
Two counters simulate any number of counters
Two stacks simulate a tape
One tape simulates two tapes
Regular languages
Regular expressions, DFRs, DFAs & NFAs define the same class of languages.
Epsilon-transitions can be eliminated.
Minimization of DFRs and Myhill-Nerode Theorem
Closure properties
Pumping lemmas
Context-free Languages
(Left- and right-)regular grammars accept exactly the regular languages.
Context-free grammars; parse trees, derivations and least solutions.
Example of an inherently ambiguous language
Eliminating useless productions, useless symbols, epsilon productions
Chomsky normal form
Greibach normal form
Pushdown automata (NSAs) accept exactly the CFL.
Closure properties (union, concatenation, star, reversal, fin, transducers,
intersection with a regular language; not closed under complementation)
Pumping lemmas & Ogden's lemma
Algorithms for deciding finiteness, emptiness and membership
"Deterministic" CFG accept more than the DCFL (defined with DSAs or DSRs)
-----------------8<------------Midterm------------Start CS154n--------------
Computability
Turing machines and variations (two-way, multitape, etc.)
Recursive and r.e. languages; partial and total recursive functions
Church's thesis
* Turing computability = Herbrand-Goedel computability
Writing Turing machine programs
Recursive languages closed under intersection, union and complement.
R.e. languages closed under intersection and union, but not complement.
Other closure properties (concatenation, star, [perfect] shuffle, transd.)
Language recursive iff it and its complement r.e.
The r.e. languages are the projections of recursive languages
A language is r.e. iff it is the range of a [nondecreasing] rec. function
* R.e. languages are exactly the ones generated by unrestricted grammars.
* Context sensitive languages (grammars); strictness of the Chomsky hierarchy
* Linear bounded automata accept exactly the CSL.
Universal TM
the halting problem is undecidable
the total recursive functions cannot be enumerated exactly
reduction of one problem to another
r.e. complete languages (or problems)
the Post Correspondence Problem
some undecidable problems, e.g.:
validity in first-order logic
the empty intersection problem for context-free grammars
the ambiguity problem for context-free grammars (and languages)
the question whether or not a CFG generates all strings
* Matijasevic's Diophantine Theorem
Rice's Theorem: Every nontrivial question about the functional
behavior of Turing machines is undecidable
Recursion theorem & fixed-point theorem
Goedels incompleteness theorem
* Oracles, Turing reductions and the arithmetical hierarchy
Complexity
The classes DSPACE(f), NSPACE(f), DTIME(f) and NTIME(f) for
integer functions f.
If c>0 is a constant then DSPACE(f) = DSPACE(cf)
and if O(f) > O(n) then also DTIME(f) = DTIME(cf)
DTIME(f) < NTIME(f) and DTIME(f) < DSPACE(f) < NSPACE(f) < DSPACE(f^2).
If L is in NTIME(f), then there is a constant d such that L in DTIME(d^f).
If L is in DSPACE(f) with f(n) > log(n), then L in DTIME(d^f) for some d.
The classes P and NP. The class PSPACE.
Polynomial time reducibility. NP-completeness. PSPACE completeness.
Cooks Theorem: Satisfiability is NP-complete.
Other NP-complete problems: 3SAT, traveling salesman, partition,
clique, Hamiltonian cycle, vector sum, ...
Some PSPACE complete problems