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