# CYK / CKY: complete charts, backpointers and ambiguity

Subject: Natural Language Processing

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/nlp/#tee/formulas/f-deep-u4-forward-cky/cky

Canonical: https://deep-learning-study-room.vercel.app/read/nlp/tee/formulas/f-deep-u4-forward-cky--cky/

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.
$$



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 j | 1: the | 2: cat | 3: eats | 4: a | 5: fish |
| --- | --- | --- | --- | --- | --- |
| 1 | Det | NP | ∅ | ∅ | S |
| 2 | — | N | ∅ | ∅ | ∅ |
| 3 | — | — | V | ∅ | VP |
| 4 | — | — | — | Det | NP |
| 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.