Prerequisites by Topic

• Experience doing formal reasoning about automata, grammars, and
  formal languages
• Understanding of basic concepts of set theory, functions and
  relations, and propositional
  and predicate logic
• Ability to write rigorous proofs

Knowledge and Skills Acquired

• Mastery of:
  • Properties of regular languages, and context-free languages
  • Use and properties of regular expressions, finite automata,
    nondeterministic finite automata, context-free grammars, and
    pushdown automata
  • Techniques for proving facts regarding the above concepts
  • Written communication of solutions to language theory
    problems
• Familiarity with:
  • Properties of deterministic context-free, context-sensitive,
    recursive, and recursively enumerable languages
  • Use and properties of deterministic pushdown automata and
    Turing machines
  • Techniques for constructing Turing machines and proving
    undecidability results