Natural Language Processing · TEE · formulas

Prepare a grammar for CYK / CKY

Faculty topic: CNF and CYK / CKY parsing

Unit 4 PDF p105 names CYK. The supplied papers ask top-down / bottom-up CFG trees, not CKY charts. These traces explain the taught topic.

Faculty topic; not an observed numerical PYQ. Unit 4 PDF p105 names CYK. The supplied papers ask top-down / bottom-up CFG trees, not CKY charts. These traces explain the taught topic.

CYK and CKY are two names for the same dynamic-programming parsing family. A chart stores which grammatical categories can generate each contiguous span of the sentence. Small spans are solved first and reused to build larger spans. Basic CKY uses a context-free grammar in Chomsky normal form (CNF): a production has either two nonterminals on its right, A→B C, or one terminal, A→word. Empty-string handling is a separate special case; the examples here have no empty production.

Rule	Basic CKY status	Reason
S → NP VP	Allowed	Two nonterminals
N → cat	Allowed	One terminal
NP → Det Adj N	Convert first	Three nonterminals
NP → N	Eliminate or handle unary closure	One nonterminal, not a lexical terminal
VP → eats NP	Convert first	Mixed terminal and nonterminal

Question. Convert NP→Det Adj N, NP→N, N→cat and VP→eats NP into basic CNF-compatible productions. Preserve their possible word yields. [Authored worked example]

Answer

Given

The symbols NP,Det,Adj,N,VP are nonterminals; cat and eats are terminals. Other needed lexical rules remain as supplied.

To find

Equivalent binary or terminal productions for these cases.

Formula and why it applies

Introduce helper categories for a long right-hand side or a terminal mixed with nonterminals. Eliminate a unary nonterminal rule by inheriting the reachable non-unit productions.

Solution

Step 1. Binarize the three-part NP

Introduce X: NP→Det X and X→Adj N. X is a helper, not a word; the terminal order remains Det, Adj, N.

Step 2. Remove the unit production

NP→N and N→cat allow NP to derive cat. Add NP→cat, retain N→cat where needed, and remove NP→N. With more rules reachable through unit chains, inherit every corresponding non-unit rule, not only the first one.

Step 3. Replace the mixed terminal

Introduce Vlex→eats and replace VP→eats NP by VP→Vlex NP.

Step 4. Read the converted forms

NP→Det X | cat; X→Adj N; N→cat; VP→Vlex NP; Vlex→eats. All displayed productions are binary nonterminal or single-terminal rules.

Final answer. The converted rules preserve the original word sequences while satisfying the displayed basic CKY forms. Helper nodes change tree shape; they can be removed when presenting the original grammar’s tree.

General CNF conversion may also require eliminating nullable productions and useless symbols while preserving the intended language. Do not claim that simply splitting long rules handles every arbitrary CFG. An Earley parser instead supports general CFG rules using prediction, scanning and completion; it combines top-down expectations with bottom-up evidence. LR and operator-precedence parsers are other methods named in the faculty list, with grammar restrictions of their own.