CYK Algorithm
CYK Algorithm is a membership algorithm of context free grammar. 
 It is used to decide whether a given string belongs to the language of grammar or not.
 It is also known as CKY Algorithm or CockeYoungerKasami Algorithm after its inventors.
Important Notes
Note01:
 CYK Algorithm operates only on Context Free Grammars given in Chomsky Normal Form.
Note02:
 The worst case running time of CYK Algorithm is Θ (n^{3}.G).
 Here, n = Length of parsed string and G = Size of the CNF Grammar G.
Algorithm
Begin for ( i = 1 to n do ) Vi1 { A  A → a is a production where ith symbol of x is a } for ( j = 2 to n do ) for ( i = 1 to n  j + 1 do ) Begin Vij = ϕ For k = 1 to j  1 do Vij = Vij ∪ { A  A → BC is a production where B is in Vik and C is in V(i + k)(j  k) } End End
Also Read Algorithm To Check Whether CFL is Empty
Deciding Membership Using CYK Algorithm
To decide the membership of any given string, we construct a triangular table where
 Each row of the table corresponds to one particular length of sub strings.
 Bottom most row corresponds to strings of length1.
 Second row from bottom corresponds to strings of length2.
 Third row from bottom corresponds to strings of length3.
 Top most row from bottom corresponds to the given string of lengthn.
Example
For a given string “x” of length 4 units, triangular table looks like
We will fill each box of x_{ij} with its V_{ij}.
These notations are discussed below.
Notations Used
Notation01: x_{ij}
x_{ij} represents a sub string of “x” starting from location ‘i’ and has length ‘j’. Example Consider x = abcd is a string, then Number of sub strings possible = n(n+1)/2 = 4 x (4+1) / 2 = 10 We have
Notation02: V_{ij}
V_{ij} represents a set of variables in the grammar which can derive the sub string x_{ij.} If the set of variables consists of the start symbol, then it becomes sure

Also Read Algorithm To Check Whether CFL is Finite
PRACTICE PROBLEM BASED ON CYK ALGORITHM
Problem
For the given grammar, check the acceptance of string w = baaba using CYK Algorithm
S → AB / BC
A → BA / a
B → CC / b
C → AB / a
Solution
First, let us draw the triangular table.
 The given string is x = baaba.
 Length of given string = x = 5.
 So, Number of sub strings possible = (5 x 6) / 2 = 15.
So, triangular table looks like
Now, let us find the value of V_{ij} for each cell.
For Row1:
Finding V_{11}
 V_{11} represents the set of variables deriving x_{11}.
 x_{11} = b.
 Only variable B derives string “b” in the given grammar.
 Thus, V_{11} = { B }
Finding V_{21}
 V_{21} represents the set of variables deriving x_{21}.
 x_{21} = a.
 Variables A and C derive string “a” in the given grammar.
 Thus, V_{21} = { A , C }
Finding V_{31}
 V_{31} represents the set of variables deriving x_{31}.
 x_{31} = a.
 Variables A and C derive string “b” in the given grammar.
 Thus, V_{31} = { A , C }
Finding V_{41}
 V_{41} represents the set of variables deriving x_{41}.
 x_{41} = b.
 Only variable B derives string “b” in the given grammar.
 Thus, V_{41} = { B }
Finding V_{51}
 V_{51} represents the set of variables deriving x_{51}.
 x_{51} = a.
 Variables A and C derives string “a” in the given grammar.
 Thus, V_{51} = { A , C }
For Row2
RULEAs per the algorithm, to find the value of V_{ij} from 2^{nd} row on wards, we use the formula V_{ij} = V_{ik} V_{(i+k)(jk)} where k varies from 1 to j1 
Finding V_{12}
We have i = 1 , j = 2 , k = 1
Substituting values in the formula, we get
V_{12} = V_{11}. V_{21}
V_{12} = { B } { A , C }
V_{12} = { BA , BC }
∴ V_{12} = { A , S }
Finding V_{22}
We have i = 2 , j = 2 , k = 1
Substituting values in the formula, we get
V_{22} = V_{21}. V_{31}
V_{22} = { A , C } { A , C }
V_{22} = { AA , AC , CA , CC }
Since AA , AC and CA do not exist, so we have
V_{22} = { CC }
∴ V_{22} = { B }
Finding V_{32}
We have i = 3 , j = 2 , k = 1
Substituting values in the formula, we get
V_{32} = V_{31}. V_{41}
V_{32} = { A , C } { B }
V_{32} = { AB , CB }
Since CB does not exist, so we have
V_{32} = { AB }
∴ V_{32} = { S , C }
Finding V_{42}
We have i = 4 , j = 2 , k = 1
Substituting values in the formula, we get
V_{42} = V_{41}. V_{51}
V_{42} = { B } { A , C }
V_{42} = { BA , BC }
∴ V_{42} = { A , S }
For Row3
Finding V_{13}
We have i = 1 , j = 3 , k = 1 to (31) = 1,2
Substituting values in the formula, we get
V_{13} = V_{11}. V_{22} ∪ V_{12}. V_{31}
V_{13} = { B } { B } ∪ { A , S } { A , C }
V_{13} = { BB } ∪ { AA , AC , SA , SC }
Since BB , AA , AC , SA and SC do not exist, so we have
V_{13} = ϕ ∪ ϕ
∴ V_{13} = ϕ
Finding V_{23}
We have i = 2 , j = 3 , k = 1 to (31) = 1,2
Substituting values in the formula, we get
V_{23} = V_{21}. V_{32} ∪ V_{22}. V_{41}
V_{23} = { A , C } { S , C } ∪ { B } { B }
V_{23} = { AS , AC , CS , CC } ∪ { BB }
Since AS , AC , CS and BB do not exist, so we have
V_{23} = { CC }
∴ V_{23} = B
Finding V_{33}
We have i = 3 , j = 3 , k = 1 to (31) = 1,2
Substituting values in the formula, we get
V_{33} = V_{31}. V_{42} ∪ V_{32}. V_{51}
V_{33} = { A , C } { A , S } ∪ { S , C } { A , C }
V_{33} = { AA , AS , CA , CS } ∪ { SA , SC , CA , CC }
Since AA , AS , CA , CS , SA , SC and CA do not exist, so we have
V_{33} = ϕ ∪ { CC }
V_{33} = ϕ ∪ { B }
∴ V_{33} = { B }
For Row4
Finding V_{14}
We have i = 1 , j = 4 , k = 1 to (41) = 1,2,3
Substituting values in the formula, we get
V_{14} = V_{11}. V_{23} ∪ V_{12}. V_{32} ∪ V_{13}. V_{41}
V_{14} = { B } { B } ∪ { A , S } { S , C } ∪ { ϕ , B }
V_{14} = { BB } ∪ { AS , AC , SS , SC } ∪ { B }
Since BB , AS , AC , SS , SC and B do not exist, so we have
V_{14} = ϕ ∪ ϕ ∪ ϕ
∴ V_{14} = ϕ
Finding V_{24}
We have i = 2 , j = 4 , k = 1 to (41) = 1,2,3
Substituting values in the formula, we get
V_{24} = V_{21}. V_{33} ∪ V_{22}. V_{42} ∪ V_{23}. V_{51}
V_{24} = { A , C } { B } ∪ { B } { A , S } ∪ { B } { A , C }
V_{24} = { AB , CB } ∪ { BA , BS } ∪ { BA , BC }
Since CB does not exist, so we have
V_{24} = { AB } ∪ { BA , BS } ∪ { BA , BC }
V_{24} = { S , C } ∪ { A } ∪ { A , S }
∴ V_{24} = { S , C , A }
For Row5
Finding V_{15}
We have i = 1 , j = 5 , k = 1 to (51) = 1,2,3,4
Substituting values in the formula, we get
V_{15} = V_{11}. V_{24} ∪ V_{12}. V_{33} ∪ V_{13}. V_{42} ∪ V_{14}. V_{51}
V_{15} = { B } { S , C , A } ∪ { A , S } { B } ∪ { ϕ } { A , S } ∪ { ϕ } { A , C }
V_{15} = { BS , BC , BA } ∪ { AB , SB } ∪ { A , S } ∪ { A , C }
Since BS , SB , A , S and C do not exist, so we have
V_{15} = { BC , BA } ∪ { AB } ∪ ϕ ∪ ϕ
V_{15} = { S , A } ∪ { S , C } ∪ ϕ ∪ ϕ
∴ V_{15} = { S , A , C }
Now,
 The value of V_{ij} is computed for each cell.
 We observe V_{15} contains the start symbol S.
 Thus, string x_{15} = baaba is a member of the language of given grammar.
After filling the triangular table, it looks like
Results From Triangular Table
The following important results can be made from the above triangular table
Result01:
 There exists total 4 distinct sub strings which are members of the language of given grammar.
 These 4 sub strings are ba, ab, aaba, baaba.
 This is because they contain start symbol in their respective cell.
Result02:
 Strings which can not be derived from any variable are baa, baab.
 This is because they contain ϕ in their respective cell.
Result03:
 Strings which can be derived from variable B alone are b, aa, aba, aab.
 This is because they contain variable B alone in their respective cell.
Get more notes and other study material of Theory of Automata and Computation.
Watch video lectures by visiting our YouTube channel LearnVidFun.