Theory of Computation · topic
Derivations, sentential forms, parse trees, leftmost and rightmost derivations, ambiguity and inherent ambiguity, grammar to language, removal of useless, epsilon and unit productions in the right order, Chomsky and Greibach normal forms with derivation lengths, and CYK membership.
A context-free grammar (CFG) generates a language by rewriting nonterminals one at a time, independently of surrounding context. The languages of CFGs are the context-free languages (CFLs), recognized by pushdown automata.
Before algorithms such as CYK or proofs such as the CFL pumping lemma, grammars are cleaned: remove useless symbols, ε-productions (when ε ∉ L), and unit productions, then convert to Chomsky normal form (CNF) or Greibach normal form (GNF).
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
