Key Theorems and Examples

• A listing of the formal definitions for Big-Oh, Omega, Theta and little-Oh.
  
  
• A proof that the Halting Problem is unsolvable.
  
  
• A proof illustrating the existence of non-recursively enumerable languages.
  
  
• A proof that the power set of a countable set is uncountable.
  
  
• The two proofs showing the CFG <-> PDA equivalence. Furthermore here are two examples of how to go from a PDA into a CFG for the same language.
  
  
• Kleene's Theorem: the proof that for every DFA there exists an equivalent regular language representing the same language recognized by the DFA. This theorem is the second half of the proof that DFA's are equivalent to regular expressions/languages.
  
  
• The proof that for every NFA (without epsilon transitions) there exists an equivalent DFA which accepts the same language.