Theoretical Computer Science Exam #2 Review

Material Covered in Exam 2

Context-Free Languages, relation to Regular Languages

Context-Free Grammars

   rewrite rule, terminal symbol, nonterminal symbol, context-free grammar
   ->G, =>G, language generated by G
   derivation, length of a derivation, number of steps in a derivation
   parse trees, leftmost derivation, rightmost derivation, ambiguity

Pushdown Automata

   transition rules, string acceptance
   state diagram, configuration
   yields in 1 step, yields in any number of steps
   equivalence of techniques, CFG -> PDA

Properties of Context-Free Languages

   Chomsky Normal Form
   Identify / remove e-productions, nullable, identify / remove unit productions
   Identify / remove useless symbols
   Pumping Lemma for Context-Free Languages
   CFL closures:  union, concatenation, Kleene closure, NOT complementation,
                  NOT intersection

Decision Algorithms for Context-Free Languages

   Determine if L(G) empty, determing if L(G) finite
   Determing if w in L(G) (CYK algorithm)

Lex and Yacc (what are they, what type of rules do they contain)

Turing Machines

   transition rules, string acceptance
   state diagram, configuration

Context sensitive languages

Recursive Languages

Recursively Enumerable Languages