Natural Language Processing · TEE · formulas

CYK / CKY: complete charts, backpointers and ambiguity

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.

Number the words 1 to n. Let T[i,j] contain all categories that derive the span from word i through word j, inclusive. Start with one-word cells from lexical rules. For every longer span try every split k between i and j: if B belongs to T[i,k], C belongs to T[k+1,j], and A→B C is a rule, put A in T[i,j]. Store the rule and split as backpointers when a tree is required.

A\in T[i,j]\quad\text{if}\quad A\to BC,\ B\in T[i,k],\ C\in T[k+1,j],\ i\le k<j.LaTeX: A\in T[i,j]\quad\text{if}\quad A\to BC,\ B\in T[i,k],\ C\in T[k+1,j],\ i\le k<j.

Accept precisely when S is in T[1,n]. Empty cells are meaningful: no category in this grammar derives that span. Basic recognition takes O(n³|G|) time using the straightforward rule-loop analysis and O(n²|N|) category storage; packed backpointers can preserve alternative parses without listing all trees immediately.

Question. Use CKY to parse “the cat eats a fish” with S→NP VP, NP→Det N, VP→V NP; Det→the|a; N→cat|fish; V→eats. Show the complete span chart and reconstruct a tree. [Authored worked example]

Answer

Given

Words 1=the, 2=cat, 3=eats, 4=a, 5=fish. The grammar is already in the basic CNF form. ∅ denotes an empty cell.

To find

All chart cells, acceptance, and a parse tree.

Formula and why it applies

Fill lexical cells, then spans of length 2,3,4,5. For each span try all split points and combine only categories permitted by a binary grammar rule.

Solution

Step 1. Fill the five one-word cells

T[1,1]={Det}; T[2,2]={N}; T[3,3]={V}; T[4,4]={Det}; T[5,5]={N}.

Step 2. Fill length-two spans

T[1,2]={NP} because Det+N matches NP→Det N. T[2,3]=∅ (N V has no rule). T[3,4]=∅ (V Det has no rule). T[4,5]={NP} using Det+N.

Step 3. Fill length-three spans

T[1,3]=∅: neither Det+(N eats) nor NP+V matches a rule. T[2,4]=∅. For T[3,5], split after word 3: V from [3,3] plus NP from [4,5] gives VP. Thus T[3,5]={VP}; the other split has an empty left child.

Step 4. Fill length-four spans

T[1,4]=∅ because every split has an empty child or an unmatched category pair. T[2,5]=∅: the only wholly nonempty possibility is N+VP, and no rule produces a parent from that pair.

Step 5. Fill the complete span

For T[1,5], k=1 has an empty right cell; k=2 gives NP from [1,2] and VP from [3,5], hence S. k=3 and k=4 have empty left cells. Therefore T[1,5]={S}.

Step 6. Copy the completed upper-triangular chart
Start i / end j1: the2: cat3: eats4: a5: fish
1DetNP∅∅S
2—N∅∅∅
3——V∅VP
4———DetNP
5————N

A dash is outside the chart (i>j); ∅ is an evaluated but empty valid span. Read the chart by increasing span length, not left-to-right across a row.

Step 7. Follow the stored backpointers

S[1,5]→NP[1,2] VP[3,5]; NP[1,2]→Det[1,1] N[2,2]; VP[3,5]→V[3,3] NP[4,5]; NP[4,5]→Det[4,4] N[5,5].

S
├── NP
│   ├── Det: the
│   └── N: cat
└── VP
    ├── V: eats
    └── NP
        ├── Det: a
        └── N: fish
Final answer. Accepted because S∈T[1,5]. The reconstructed tree’s leaves are exactly the five input words in order.

Question. A grammar has S→A A, A→A A and A→a. Use CKY for “a a a” and explain how two parse trees are preserved. [Authored worked example]

Answer

Given

Three identical terminal tokens. S is the start symbol. No unit or empty rules are present.

To find

Chart categories and both successful split choices for the root.

Formula and why it applies

A chart cell is a set of possible categories. For each category keep all successful backpointers when the task requires every parse.

Solution

Step 1. Initialize the diagonal

Each of T[1,1], T[2,2], T[3,3] is {A}, from A→a.

Step 2. Fill two-word spans

T[1,2] and T[2,3] each contain {A,S}: A+A can use A→A A or S→A A.

Step 3. Try both root splits

k=1: A[1,1] + A[2,3] permits S. k=2: A[1,2] + A[3,3] also permits S. The complete cell is {A,S}, but S has two distinct backpointer alternatives.

Step 4. Draw both bracketed trees

[S [A a] [A [A a] [A a]]] and [S [A [A a] [A a]] [A a]]. Both yield a a a; the constituent grouping differs.

Final answer. Accepted, with two S-rooted parses. A category appearing once in a set does not mean there is only one derivation.

Question. With S→NP VP, NP→Det N, VP→V NP; Det→the|a; N→cat|fish; V→eats, test “the eats cat” using CKY. [Authored worked example]

Answer

Given

Tokens are the/eats/cat, with no punctuation. Use exactly the supplied grammar.

To find

Whether the grammar accepts the whole input.

Formula and why it applies

A parse exists only if the complete chart cell contains the start symbol.

Solution

Step 1. Initialize the diagonal

T[1,1]={Det}; T[2,2]={V}; T[3,3]={N}.

Step 2. Try length-two combinations

Det+V matches no binary rule; V+N also matches no rule (VP requires V+NP). Both two-word cells are empty.

Step 3. Try the two full-span splits

Each split has an empty child, so T[1,3]=∅ and S is absent.

Final answer. Rejected by this grammar. Do not invent NP→N to force acceptance. Grammar rejection and a universal judgment about every possible English grammar are different claims.

Yaad rakho: Diagonal par words ke tags; phir chhote spans jodo. Har split dekho. Full sentence cell mein S aaya toh parse possible.