Theory of Computation
Topic Outline
Final Examination

The final examination for the Theory of Computation in the Fall of 2000 will be held on December 14th at 2:00pm.
 
  1. Basic Terms
    1. String
    2. Alphabet
    3. Language
  2. Regular Languages
    1. DFSA
    2. NDFSA
    3. Regular Expressions
    4. GNDFS
    5. Table view of automata
    6. Diagram view of automata
    7. Definitions
    8. String acceptance
    9. Conversions
      1. NDFSA to DFSA
      2. DFSA to GNDFSA
      3. GNDFSA to regular expression
      4. regular expression to NDFSA
  3. Context Free Languages
    1. Context Free Grammar
      1. Definition
      2. Parse Tree
      3. Derivation
      4. ambiguous
    2. Pushdown automata
      1. definition
      2. table form
      3. string acceptance
      4. CFG as pushdown automata
    3. Conversion from regular expression to CFG
  4. Turing machine
    1. Definition
    2. String acceptance
    3. Decidable languages
    4. Recognizable languages