0 Todo

	Review Quizzes

	Review Midterm

	Review Homework

	I will put up solutions

1 Regular Languages

	Know all the algorithms you learned and how fast they are.
	I won't make you do them.

	RE -> NFA
	complement, union, intersect, concatenate
	NFA -> DFA 
	DFA -> minimal DFA
	NFA -> RE
	Run NFA on string.

	Example of small NFA that blows up to big DFA.

	Given RE R and string w, does R generate w?

	Pumping lemma.  I will make you do this.

2 Context-Free Languages

	Make sure you review my notation.

	Write a CFG for a language.
	Convert it to a PDA.

	Write a PDA for a language.
	Convert it to a CFG.

	Ambiguous grammars.

	Convert CFG to Chomsky Normal Form.

	Does CNF CFG generate a string?
	Do it!  Dynamic programming algorithm.

	Pumping lemma.

3 Turing Machines

	Write or hand-simulate a simple Turing.java program.

	Simulate multi-tape TM:  the idea and running time.

	Simulate NTM:  the idea and running time.

4 Decidability

	Recognize vs. Decide

	Diagonalization.

	Countable vs. Uncountable infinity.
	Set of strings is countable.
	A language is a subset of the set of all strings.
	How many languages are there?  Uncountable infinity.
	How many TMs are there?  Countable!  (Each is string.)
	There are lots and lots of languages which have no TM.

	The halting problem is undecidable.

	Unrecognizable language.

5 Reductions

	Minimizing CFG is ``undecidable''.

  	Definition of reduction f.

	Rice's theorem.

7 Time Complexity

	P, NP, NP-hard, NP-complete definitions
	The *complement* of PARTITION or any NP-complete problem may not even be in NP.

	Languages in P

		RELPRIME:  run Euclid's algorithm

		Every context-free language....

		2-SAT:  run the algorithm (do it!)

		PRIME, COMPOSITE

	Languages in NP but probably not NP-complete

		FACTOR = { (n,r) | n has a prime factor p <= r }
		FACTOR is in Quantum-P

	TILING
		Definition
		Idea of reduction from every other language in NP.

	TILING -> SAT

	SAT -> 3-SAT

	3-SAT -> 1in3-SAT -> PARTITION

	3-SAT -> { R | L(R) != (0+1)^n }

	Minimizing RE is ``NP-hard''

	3-SAT -> CLIQUE (and INDEPENDENT SET!)

	3-SAT -> VERTEX-COVER

	3-SAT -> HAMPATH

	PARTITION -> POLYGON-PACKING