TOC- Assignment-2

K. Vishnu Raj
Lecture notes- April 2026

1 Fully Worked Solution Key: CYK Algorithm

AA
for CNF Grammars There is no production of the form:
1.1 Overview of the CYK Algorithm Y → AA
The Cocke–Younger–Kasami (CYK) algorithm is a dynamic programming algo-
Hence:
rithm used to test whether a string belongs to a context-free grammar written
in Chomsky Normal Form (CNF). T [1, 2] = ∅
A grammar is in CNF if every production is of the form: —
Now consider:
A → BC
or w2 w3 = ab
Possible split:
A→a
where A, B, C are non-terminals and a is a terminal. a|b
For a string
T [2, 1] × T [3, 1] = {A} × {B}
w = w1 w2 · · · wn
This gives:
the CYK algorithm constructs a triangular parsing table T [i, j], where:
AB
T [i, j]
Since:
contains all non-terminals that can derive the substring of length j starting
from position i. S → AB
That is, we get:
∗
T [i, j] = {A | A ⇒ wi wi+1 · · · wi+j−1 } T [2, 2] = {S}
The input string is accepted if the start symbol S appears in the topmost cell: —
Now consider:
S ∈ T [1, n]
— w3 w4 = bb
2 Example 1: CYK Parsing for Grammar G Possible split:
1
2.1 Grammar in CNF b|b
Consider the CNF grammar:
T [3, 1] × T [4, 1] = {B} × {B}
S → AX | AB This gives:
X → SB BB
There is no production:
A→a
Y → BB
B→b Therefore:
This grammar generates strings of the form: T [3, 2] = ∅
n n
a b —
for n ≥ 1. 2.5 Step 3: Fill Substrings of Length 3
— Now consider substrings of length 3.
2.2 Input String First:
Let the input string be: w1 w2 w3 = aab
w = aabb Possible splits are:
The length of the string is: a | ab
n=4 and
The symbols are indexed as follows:
aa | b
w1 = a, w2 = a, w3 = b, w4 = b For the first split:
—
T [1, 1] × T [2, 2] = {A} × {S}
2.3 Step 1: Initialization
For substrings of length 1, we check which variables produce each terminal. This gives:
The terminal productions are: AS
A→a There is no production:

B→b Y → AS
Therefore: For the second split:

T [1, 1] = {A} T [1, 2] × T [3, 1] = ∅ × {B}

This gives no valid combination.
T [2, 1] = {A} Therefore:
T [1, 3] = ∅
T [3, 1] = {B}
—
Now consider:
T [4, 1] = {B}
— w2 w3 w4 = abb
2.4 Step 2: Fill Substrings of Length 2 Possible splits are:
Now consider all substrings of length 2. a | bb
w1 w2 = aa and
Possible split:
ab | b
a|a For the first split:
So we combine:
T [2, 1] × T [3, 2] = {A} × ∅
T [1, 1] × T [2, 1] = {A} × {A} No valid combination is obtained.
This gives: For the second split:

1
 T [2, 2] × T [4, 1] = {S} × {B} S→B
This gives: and
SB B→b
Since: we may record S for terminal b if unit productions have been removed by
replacing S → B with:
X → SB
S→b
we get:
Thus:
T [2, 3] = {X}
T [1, 1] = {A}
—
2.6 Step 4: Fill Substring of Length 4 T [2, 1] = {B, S}
Now consider the complete string: —
w1 w2 w3 w4 = aabb 3.4 Step 2: Fill Substrings of Length 2
Possible splits are: Now consider the full string:
a | abb ab
Possible split:
aa | bb
a|b
aab | b
T [1, 1] × T [2, 1] = {A} × {B, S}
For the first split:
This gives the combinations:
T [1, 1] × T [2, 3] = {A} × {X}
AB, AS
This gives: Now check the grammar rules.
AX There is no production:
Since: Y → AB
S → AX and there is no production:
we get: Y → AS
S ∈ T [1, 4] Therefore:
For the second split: T [1, 2] = ∅
—
T [1, 2] × T [3, 2] = ∅ × ∅
No valid combination is obtained.
3.5 Final CYK Table
For the third split: Length 1 2
2 ∅
T [1, 3] × T [4, 1] = ∅ × {B} 1 {A} {B, S}
No valid combination is obtained. —
Therefore: 3.6 Final Decision
T [1, 4] = {S} Since:
— S∈
/ T [1, 2]
2.7 Final CYK Table the string is rejected.
Length 1 2 3 4 Therefore:
4 {S}
3 ∅ {X} ab ∈
/ L(G2 )
2 ∅ {S} ∅ —
1 {A} {A} {B} {B} 4 Example 3: CYK Parsing for String abb
—
2.8 Final Decision 4.1 Grammar
Since the start symbol S appears in the top cell: Use the same CNF grammar:

S ∈ T [1, 4] S → AX1 | b
the string is accepted. X1 → SB
Therefore:
aabb ∈ L(G1 ) A→a
—
B→b
3 Example 2: CYK Parsing for Grammar G2 —
3.1 Grammar in CNF 4.2 Input String
Consider the CNF grammar: w = abb
The indexed symbols are:
S → AX1 | B
w1 = a, w2 = b, w3 = b
X1 → SB —
A→a 4.3 Step 1: Initialization
Using:
B→b A→a
This grammar corresponds to the original structure:
S → aSb | b B→b
— S→b
3.2 Input String we get:
Let the input string be:
T [1, 1] = {A}
w = ab
The length of the string is: T [2, 1] = {B, S}
n=2 T [3, 1] = {B, S}
The indexed symbols are: —
w1 = a, w2 = b 4.4 Step 2: Substrings of Length 2
— First consider:
3.3 Step 1: Initialization w1 w2 = ab
The terminal productions are:
T [1, 1] × T [2, 1] = {A} × {B, S}
A→a
Possible combinations:
B→b AB, AS
Also, since: There is no rule producing AB or AS. Hence:

2
 T [1, 2] = ∅ w1 = id, w2 = +, w3 = id
— The length is:
Now consider:
n=3
w2 w3 = bb —
T [2, 1] × T [3, 1] = {B, S} × {B, S} 5.3 Step 1: Initialization
The terminal productions are:
Possible combinations:
E → id
BB, BS, SB, SS
Since: P →+
X1 → SB Hence:
we get: T [1, 1] = {E}
T [2, 2] = {X1 }
T [2, 1] = {P }
—
4.5 Step 3: Substring of Length 3 T [3, 1] = {E}
Now consider the full string: —
abb 5.4 Step 2: Substrings of Length 2
Possible splits are: First consider:
a | bb w1 w2 = id+
and Possible split:

ab | b id | +
For the first split: T [1, 1] × T [2, 1] = {E} × {P }
T [1, 1] × T [2, 2] = {A} × {X1 } This gives:
This gives: EP
AX1 There is no production:
Since: Y → EP
S → AX1 Therefore:
we get: T [1, 2] = ∅
S ∈ T [1, 3] —
Now consider:
For the second split:
w2 w3 = +id
T [1, 2] × T [3, 1] = ∅ × {B, S} Possible split:
No valid combination is obtained.
Therefore: + | id
T [1, 3] = {S} T [2, 1] × T [3, 1] = {P } × {E}
— This gives:
4.6 Final CYK Table
Length 1 2 3 PE
3 {S} Since:
2 ∅ {X1 } X → PE
1 {A} {B, S} {B, S}
— we get:
4.7 Final Decision T [2, 2] = {X}
Since: —
S ∈ T [1, 3]
5.5 Step 3: Substring of Length 3
Now consider the complete string:
the string is accepted.
Therefore: id + id
abb ∈ L(G2 ) Possible splits are:
— id | +id
5 Example 4: CYK Parsing for Arithmetic Ex- and
pression Grammar id+ | id
5.1 Grammar in CNF For the first split:
Consider the grammar:
T [1, 1] × T [2, 2] = {E} × {X}
E → E + E | id This gives:
To apply CYK, convert it into CNF.
Let: EX
Since:
I → id
E → EX
P →+ we get:
The rule:
E ∈ T [1, 3]
E →E+E For the second split:
has three symbols on the right-hand side. Replace it as:
T [1, 2] × T [3, 1] = ∅ × {E}
E → EX No valid combination is obtained.
Therefore:
X → PE
Thus the CNF grammar is: T [1, 3] = {E}
—
E → EX | id
5.6 Final CYK Table
X → PE Length 1 2 3
3 {E}
P →+ 2 ∅ {X}
1 {E} {P } {E}
—
—
5.2 Input String 5.7 Final Decision
Let the input string be:
Since the start symbol E appears in the top cell:
w = id + id
E ∈ T [1, 3]
Treat each token as one terminal symbol:
the string is accepted.

3
Therefore:
T [1, 3] = {E}
id + id ∈ L(G)
Second split:
—
6 Example 5: CYK Parsing for id + id + id T [1, 2] × T [3, 1] = ∅ × {E}
No additional symbol is obtained.
6.1 Grammar Thus:
Use the same CNF grammar:
T [1, 3] = {E}
E → EX | id —
Consider:
X → PE
w2 w3 w4 = +id+
P →+ Possible splits:
— + | id+
6.2 Input String
w = id + id + id +id | +
Token indexing:
T [2, 1] × T [3, 2] = {P } × ∅
w1 = id, w2 = +, w3 = id, w4 = +, w5 = id
Thus: T [2, 2] × T [4, 1] = {X} × {P }
n=5 This gives:
— XP
6.3 Step 1: Initialization No rule derives XP . Therefore:
Using: T [2, 3] = ∅
E → id —
Consider:
P →+ w3 w4 w5 = id + id
we obtain: Possible splits:
T [1, 1] = {E} id | +id
T [2, 1] = {P } id+ | id
T [3, 1] = {E} First split:
T [3, 1] × T [4, 2] = {E} × {X}
T [4, 1] = {P }
This gives:
T [5, 1] = {E} EX
— Since:
6.4 Step 2: Substrings of Length 2
w1 w2 = id+ E → EX

T [1, 1] × T [2, 1] = {E} × {P } = {EP } T [3, 3] = {E}

No rule derives EP , so: Second split:

T [1, 2] = ∅ T [3, 2] × T [5, 1] = ∅ × {E}

— No additional symbol is obtained.
Thus:
w2 w3 = +id
T [3, 3] = {E}
T [2, 1] × T [3, 1] = {P } × {E} = {P E} —
Since: 6.6 Step 4: Substrings of Length 4
Consider:
X → PE
w1 w2 w3 w4 = id + id+
T [2, 2] = {X} Possible splits:
—
id | +id+
w3 w4 = id+
id+ | id+
T [3, 1] × T [4, 1] = {E} × {P } = {EP }
No rule derives EP , so: id + id | +

T [3, 2] = ∅ T [1, 1] × T [2, 3] = {E} × ∅

—
T [1, 2] × T [3, 2] = ∅ × ∅
w4 w5 = +id
T [1, 3] × T [4, 1] = {E} × {P }
T [4, 1] × T [5, 1] = {P } × {E} = {P E} This gives:
Since:
EP
X → PE No production derives EP . Hence:
T [4, 2] = {X} T [1, 4] = ∅
— —
Consider:
6.5 Step 3: Substrings of Length 3
Consider: w2 w3 w4 w5 = +id + id
Possible splits:
w1 w2 w3 = id + id
Possible splits: + | id + id
id | +id +id | +id
id+ | id +id+ | id
First split: First split:
T [1, 1] × T [2, 2] = {E} × {X} T [2, 1] × T [3, 3] = {P } × {E}
This gives: This gives:
EX PE
Since: Since:
E → EX X → PE

4
 X ∈ T [2, 4] (id + id) + id
Other splits: Therefore, the grammar:
T [2, 2] × T [4, 2] = {X} × {X} E → E + E | id
No rule derives XX. is ambiguous.
—
T [2, 3] × T [5, 1] = ∅ × {E}
No additional variable is obtained.
8 General CYK Algorithm in Mathematical
Therefore: Form
T [2, 4] = {X} Let G = (V, Σ, R, S) be a context-free grammar in CNF, and let:
— w = w1 w2 · · · wn
6.7 Step 5: Substring of Length 5 be the input string.
Now consider the full string: The CYK table is initialized as follows:

id + id + id T [i, 1] = {A | A → wi ∈ R}
Possible splits: for:
id | +id + id 1≤i≤n
For substrings of length l, where:
id+ | id + id
2≤l≤n
id + id | +id and starting position:
1≤i≤n−l+1
id + id+ | id
we compute:
First split:
l−1
T [1, 1] × T [2, 4] = {E} × {X}
[
T [i, l] = {A | A → BC, B ∈ T [i, k], C ∈ T [i + k, l − k]}
This gives: k=1

EX The string is accepted if:

Since: S ∈ T [1, n]
E → EX Otherwise, the string is rejected.
—
E ∈ T [1, 5] 9 Summary of CYK Parsing Decisions
Second split: Example Grammar Start Symbol Input String Decision
1 S aabb Accepted
T [1, 2] × T [3, 3] = ∅ × {E} 2 S ab Rejected
No result. 3 S abb Accepted
Third split: 4 E id + id Accepted
5 E id + id + id Accepted
T [1, 3] × T [4, 2] = {E} × {X} ——
This also gives: 10 Student Practice Questions
EX Practice Question 1
Again: Apply the CYK algorithm to the following CNF grammar:
E → EX S → AB | BC
so:
A → BA | a
E ∈ T [1, 5]
Fourth split: B → CC | b
T [1, 4] × T [5, 1] = ∅ × {E}
C → AB | a
No result.
Therefore: For the input string:

T [1, 5] = {E} w = baaba

— Construct the complete CYK table and decide whether:
6.8 Final CYK Table w ∈ L(G)
Length 1 2 3 4 5 —
5 {E} Practice Question 2
4 ∅ {X}
3 {E} ∅ {E} Apply the CYK algorithm to the grammar:
2 ∅ {X} ∅ {X} S → AX | AB
1 {E} {P } {E} {P } {E}
— X → SB
6.9 Final Decision
Since: A→a

E ∈ T [1, 5] B→b
the input string is accepted. For the input string:
Therefore:
w = aaabbb
id + id + id ∈ L(G) Construct the CYK table and determine whether the string is accepted.
— —
7 Educational Observation: Ambiguity Detection Practice Question 3
Apply the CYK algorithm to the arithmetic grammar:
Using CYK
The CYK table only tells us whether the string is accepted or rejected. However, E → EX | id
if multiple different split positions produce the start symbol in the top cell, X → PE
this may indicate multiple possible parse structures. P →+
For the string:
For the input string:
id + id + id w = id + id + id + id
we obtained E in the top cell from two different split patterns: Construct the CYK table and determine whether the string is accepted.
Also identify whether multiple parse structures are possible.
id | +id + id
and
id + id | +id
This corresponds to the two parse structures:
id + (id + id)
and