Theory of Computation
Topic Outline
Examination II

  1. Regular Languages
    1. Define
    2. Pumping Lemma
    3. Prove a language is not regular
  2. Context Free Grammers
    1. Definition
    2. Give grammer for a language
    3. Give a parse tree
    4. Give a derivation
    5. Ambigous grammers
    6. Convert regular expressions to grammers
  3. Pushdown Automata
    1. Definition
    2. Parse a string
    3. Treat CFG as a Pushdown atuomata
    4. Relationship between PDA and CFLs.
  4. Pumping Lemma for CFG
    1. State
    2. State contrapositive
    3. Prove a language is not context free
  5. Show a language is not regular but is context free.
  6. Other items from the first examination.