CYK Algorithm
The Cocke-Younger-
Kasami Algorithm*
Presented by:
Rishika Agarwal-220301120089
Arpita Sundaray- 220301120100
Puja Bhoi-220301120107
Scion Dilip Hazra- 220301120113
Contents
• Introduction
• Prerequisite: Chomsky Normal Form (CNF)
• Construct a Triangular Table
• Example CYK Algorithm
• (Result)
INTRODUCTION
• Full Form: Cocke-Younger-Kasami Algorithm
• Purpose: A parsing algorithm for Context-Free
Grammars (CFGs).
• Key Characteristic: It uses Dynamic Programming to
solve the problem efficiently.
• Primary Question it Answers: Given a string w and a
CFG G, does w ∈ L(G)? (Is the string a member of the
language generated by the grammar?)
• Major Constraint: The input grammar must be in
Chomsky Normal Form (CNF).
Prerequisite: Chomsky
Normal Form (CNF)
• For a CFG to be in CNF, all production rules must be of
one of two forms:
• A → BC (Non-terminal producing two non-terminals)
• A → a (Non-terminal producing a single terminal)
• Why CNF? This standardized form simplifies the
algorithm's logic and ensures it runs in a predictable
time.
• Note: Any context-free grammar (ε-free) can be
converted to CNF.
• Example of CNF Rules:
• S → AB | BC
• A → BA | a
• B → CC | b
• C → AB | a
• (The rule S → ε is also allowed only for the
start variable)
Construct a Triangular Table
• Each row corresponds to one length of substrings
• – Bottom Row – Strings of length 1
• – Second from Bottom Row – Strings of length 2
.
.
• – Top Row – string ‘w’
• Xi, i is the set of variables A such that
• A wi is a production of G
• • Compare at most n pairs of previously
• computed sets:
• (Xi, i , Xi+1, j ), (Xi, i+1 , Xi+2, j ) ... (Xi, j-1 , Xj, j )
Example CYK Algorithm
• Show the CYK Algorithm with the
following example:
• CNF grammar G
• S AB | BC
• A BA | a
• B CC | b
• C AB | a
• w is baaba
• Question Is baaba in L(G)?
S AB | BC
A BA | a
B CC | b
C AB | a
{B} {A, C} {A, C} {B} {A, C}
b a a b a
Calculating the Bottom ROW
ba
{B} {A,C}
{BA,BC}
S AB | BC
{A,S} {S,A}
A BA | a
B CC | b
C AB | a
{S, A}
{B} {A, C} {A, C} {B} {A, C}
b a a b a
aa
{A,C} {A,C}
{AA,AC,CA,CC } S AB | BC
{B} {B} A BA | a
B CC | b
C AB | a
{S, A} {B}
{B} {A, C} {A, C} {B} {A, C}
b a a b a
ab
{A,C} {B}
{AB,CB} S AB | BC
{S,C} {S,C} A BA | a
B CC | b
C AB | a
{S, A} {B} {S, C}
{B} {A, C} {A, C} {B} {A, C}
b a a b a
ba
{B} {A,C}
{BA,BC}
{A,S} {S,A}
S AB | BC
A BA | a
B CC | b
C AB | a
{S, A} {B} {S, C} {S, A}
{B} {A, C} {A, C} {B} {A, C}
b a a b a
baa
baa | baa
{B} {B} {S,A} {A,C}
{BB} empty {SA,SC,AA,AC}
emty
S AB | BC
A BA | a
B CC | b
C AB | a
Ø
{S, A} {B} {S, C} {S, A}
{B} {A, C} {A, C} {B} {A, C}
b a a b a
aab
aa b | a ab
{B} {B} {A,C} {S,C}
{BB} empty {AS,AC,CS,CC}
{B}
S AB | BC
A BA | a
B CC | b
C AB | a
Ø {B}
{S, A} {B} {S, C} {S, A}
{B} {A, C} {A, C} {B} {A, C}
b a a b a
aba
ab a | a ba
{S,C} {A,C} {A,C} {S,A}
{SA,SC,CA,CC} {AS,AA,CS,CA}
empty
{B}
S AB | BC
A BA | a
B CC | b
C AB | a
Ø {B} {B}
{S, A} {B} {S, C} {S, A}
{B} {A, C} {A, C} {B} {A, C}
b a a b a
baab
ba ab | baa b |b aab
{S,A} {S,C} Ø {B} {B} {B}
{SS,SC,AS,AC} empty
{BB}empty
empty
S AB | BC
A BA | a
B CC | b
C AB | a
Ø
Ø {B} {B}
{S, A} {B} {S, C} {S, A}
{B} {A, C} {A, C} {B} {A, C}
aaba
aa ba | aab a |a aba
{B} {S,A} {B} {A,C} {A,C} {B}
{BS,BA} {BA,BC} {AB,CB}
{A} {A,S} {S,C}
{A,S,C} {S,A,C}c
S AB | BC
A BA | a
B CC | b
C AB | a
{S, A,
Ø
C}
Ø {B} {B}
{S, A} {B} {S, C} {S, A}
{B} {A, C} {A, C} {B} {A, C}
baaba
baa ba | ba aba |baab a |b aaba
Ø {S,A} {S,A} {B} Ø {B} {B}
{S,A,C}
Empty {SB,AB} Empty
{BS,BA,BC}
{S,C} {A,S}
{S,A,C} S AB | BC
{S, A, A BA | a
C} B CC | b
{S, A, C AB | a
Ø
C}
Ø {B} {B}
{S, A} {B} {S, C} {S, A}
{B} {A, C} {A, C} {B} {A, C}
S AB | BC
A BA | a
B CC | b
C AB | a
{S, A,
X1, 5
C}
{S, A,
Ø
C}
Ø {B} {B}
{S, A} {B} {S, C} {S, A}
{B} {A, C} {A, C} {B} {A, C}
- bTable for string
a ‘w’ thatahas lengthb5 a
- The algorithm populates the triangular table
(Result)
• Is baaba in L(G)?
Yes
We can see the S in the set X 1n where ‘n’ = 5
We can see the table
the cell X15 = (S, A, C) then
if S Є X15 then baaba Є L(G)