CYK Membership Algorithm

 

CYK Membership Algorithm

CYK Algorithm is suggested by john cocke and published by Daniel H. Younger and Tadao Kasami. The letters C ,Y,K are taken from the name of the inventors.It is used to decide whether a given string belongs to the language of grammar or not.That is highly efficient parsing algorithm for context free grammars.

Example:

Consider a context free grammar G whose production rules are: S->AB|BC,  A->BA|a, B->CC|b,

C->AB|a, check the membership of string w=baaba with L(G).

Solution:- Here check w=baaba belong to the grammar or not .

Terminal b is produce in grammer production rule is B->b

Terminal a is produce in grammer production rule is A->a and C->a

ba

(B)(A,C)

(BA) and (BC)

A->BA and S->BC therefore ba nonterminal is A,S.

aa

(A,C)(A,C)

(AA),(AC),(CA),(CC)

B->CC so aa nonterminal is B.

ab

(A,C)(B)

(AB),(CB)

S->AB and C->AB

So nonterminal is S,C.

baa

b,aa    and   ba,a

(B)(B)   and  (A,S)(A,C)

(BB) and (AA),(AC),(SA),(SC)

no production produce so nonterminal  Ø.

aab

a,ab and aa,b

(A,C)(S,C) and (B)(B)

(AS),(AC),(CS),(CC) and (BB)

B->CC so nonterminal B.

aba

a,ba  and ab,a 

(A,C)(A,S) and (S,C)(A,C)

(AA),(AS),(CA),(CS) and (SA),(SC),(CA),(CC)

B->CC so nonterminal B.

baab

b,aab   and ba,ab  and baa,b

(B)(B) and (A,S)(S,C) and (∅)(B)

(BB) and (AS)(AC)(SS)(SC) and Ø

get nonterminal Ø.

aaba

a,aba and aa,ba and aab,a

(A,C)(B) and (B)(A,S) and (B)(A,C)

(AB)(CB) and (BA)(BS) and(BA)(BC)

S->AB and A->BA  and C->AB

get nonterminal S,A,C

baaba

b,aaba and  ba,aba and baa,ba and baab,a 

(B)(S,C,A) and (A,S)(B) and (Ø)(A,S) and (Ø)(A,S) and (Ø)(A,C)

(BS)(BC)(BA) and (AB)(SB) and (Ø)and (Ø) and (Ø)

S->BC and A->BA and S->AB and C->AB

get nonterminal S,A,C.

Final substring "baaba" is produced by variable S,A,C in final list of variables we have starting symbol S so w=baabaદL(G).So string belong to the grammer.