Outline for Final Exam, Spring 2007

Outline

• Concepts
  • Languages
  • Recognizers
  • Deciders
  • Verifiers
  • Reducibility
  • Inductive definitions
  • Structural induction
  • Grammars
  • Chomsky hierarchy
• Regular languages
  • Deterministic finite automata (DFAs)
  • Nondeterministic finite automata (NFAs)
  • Regular expressions
  • Regular languages are closed under union, intersection, complement, concatenation, star
  • Mechanical translations between DFAs, NFAs, regular expressions
  • Minimization of DFAs
  • Equivalence problem (for DFAs, NFAs, regular expressions) is decidable
  • Pumping lemma
• Context-free languages
  • Context-free grammars (CFGs)
  • Derivations and parse trees
  • Ambiguity, precedence, associativity
  • Closure properties
  • Pushdown Automata (PDAs)
  • NPDA vs DPDA
  • Mechanical translations from CFGs to PDAs
  • Pumping Lemma
• Turing Machines (TM)
  • Decidable and recognizable languages
  • Equivalents of Turing machines
  • Church-Turing Thesis
• Computability
  • Decidable languages
  • Undecidable languages
  • Diagonalization
  • The Halting Problem
  • Unrecognizable languages
• Complexity
  • P and NP
  • Polynomial time reductions
  • NP-completeness
  • Cook-Levin theorem

Last updated 12 April 2007.