DHARMNON-REGULAR GRAMMARS 327
Now CYK algorithm starts with CNF grammar of G. So, convert the grammar G into
CNF that is,
(+) X → a (+) R → AA
(+) Y → b (+) Q → BB
So the grammar becomes,
S → XB | YA ; X → a; R → AA;
A → a | XS | YR; Y → b; Q → BB;
B → b | YS | XQ;
Now Construct the table, i.e.,
On first column j = 1
That means only single length substrings of x is considered.
Now, xi,j ⇒ x1,1 ⇒ substring starting from Ist position and of length 1 is a,
(a bba)
Similarly, x2,1 = b (abba)X3,1 = b (abba)X4,1 = b (abba)l So, V1,1 corresponding to x1,1 means α (^) ⇒N x1,1 (where α ∈ VN of G)
(∴ x1,1 = a) so only productions are A → a and X → a.
Therefore, V1,1 = {A, X}.
l Similarly, substring x2,1 = b will be derived from productions B → b and Y → b
⇒ V2,1 = {B, Y}.
l For substring x3,1 = b ⇒ V3,1 = {B, Y} and
l for substring x4,1 = a ⇒ V4,1 = {A, X}
These entries are shown in column 1 in the table (Fig. 11.35).
Vi,1 Vi,2 Vi,3 Vi,4
i = 1 a {A, X} {S} {B} {S}
i = 2 b {B, Y} {Q} {B}
i = 3 b {B, Y} {S}
i = 4 a {A, X}
j = 1 j = 2 j = 3 j = 4
Fig. 11.35
On Second column j = 2
(substrings of length 2 is considered)
So, xi,2 are:
l x1,2 ⇒ ab (abba)