Context-Free Grammars and Constituency Parsing

19.4 Grammar equivalence and normal form

1. What is the difference between strongly and weakly equivalent grammars?
   Strongly equivalent grammars generate the same strings and assign the same phrase structure to each (up to renaming non-terminals); weakly equivalent grammars generate the same strings but assign different structures.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.4, p. 432
2. What is Chomsky normal form (CNF)?
   An ε-free grammar in which every rule is A → B C (two non-terminals) or A → a (one terminal). CNF grammars are binary branching. Any CFG can be converted into a weakly equivalent CNF grammar.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.4, p. 432
3. How is a rule A → B C D converted to CNF?
   Introduce a new non-terminal: A → B X and X → C D.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.4, pp. 432–433
4. What is Chomsky-adjunction, and how can it shrink a grammar?
   Generating a potentially infinite sequence with a rule of the form A → A B. Instead of VP → VBD NP PP, VP → VBD NP PP PP, … one can write VP → VBD NP PP and VP → VP PP.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.4, p. 433