Mathematical Foundation of Computer Science

DHARM

328 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

So, V1,2 = V1,1 * V2,1 (take the values from column one that are earlier find)

= {A, X}*{B, Y} = {AB, XB, AY and XY} we get a set of derived

symbols. Now, from r.h.s. select those entries that are found in productions of G.
only XB is found in rule of G.
Therefore, V1,2 = {S} (∴ S ⇒ XB}
Similarly,
l For x2,2 ⇒ bb (abba)
So, V2,2 = V2,1 V3,1= {B, Y}{B, Y} = {BB, YB, YY and BY}
Search for derived symbols that are in G which is BB.
Therefore, V2,2 = {Q} (∴ Q ⇒ BB}
l For x3,2 ⇒ ba (a b b a)

So, V3,2 = V3,1 * V4,1 = {B, Y}*{A, X} = {BA, YA, BX and YX}

We find derived symbol YA that are in G.

Therefore, V3,2 = {S} (∵ S ⇒ YA}

See second column of the table shown in Fig. 11.35.

On Third column j = 3

(consider only substrings of length 3)
That are,
l x1,3 ⇒ abb (a b b a)

So, V1,3 can be determine either through V1,2 V3,1 or V1,1 V2,2
That are,
{S} {B, Y} = {SB, SY} nothing is in G.
or {A, X} {Q} = {AQ, XQ}. We find derived string XQ are in rules of G
Therefore, V1,3 = {B} (∴ B ⇒ XQ}
And next possible substring is
l x2,3 ⇒ bba (a b b a)

So, V2,3 can be determined either through V2,1 * V3,2 or V2,2 * V4,1

That are,

{B, Y} * {S} = {BS, YS} we find YS is in G so no need to consider other way.

Therefore, V2,3 = {B} (∴ B ⇒ YS}

See third column of table shown in Fig. 11.35.

On last column j = 4

(complete string is considered as a whole)
l x1,4 ⇒ abba (a b b a)

So, V1,4 can be determined either through

V1,1 * V2,3 = {A, X} * {B} = {AB, XB} ⇒ XB is in G that is derived from S.