Mathematical Foundation of Computer Science

DHARM

326 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Then, xi,j and Vi,j are as follows,

Case I. for the substring of length one (xi,1 for ∀i = 1 to |x|)

n x1,1 = a and V1,1 = {A} [A ⇒ a and A ∈ VN.]

n x2,1 = b and V2,1 = {B} [B ⇒ b and * B ∈ VN.]

n x3,1 = b and V3,1 = {B} [B ⇒ b and * B ∈ VN.]

n x4,1 = a and V4,1 = {A} [A ⇒ a and A ∈ VN.]

Case II. for the substring of length two (xi,2 for ∀i = 1 to |x|-1) determine Vi,2

for all substrings xi,2. Since partition for length two (j = 2) are only 3 (|x|-

1 = 4 - 1) for string of length 4. Those are shown below,

a b b a

Case III. Similarly make next partitions for the substring of length three (xi,3 for

∀i = 1 to |x|-2) and determine Vi,3 for all the substrings xi,3.

These partitions are,

a bba

In this case two partitions are possible (|x| - 2 = 4 - 2) those are starting from position
first and second.
Case end: This is the last case for the partitioning of the substring that is completely
contains whole of the string x. for example the string of length 4 i.e. abba,
xi,4 for ∀i = 1 to | x | - 3 = 4 - 3 = 1 or x1,4 only, so, determine
V1,4 that derive the string x1,4.
a bba

The CYK algorithm stands on the way that how frequently we can determine the set of
nonterminals Vi,j for each case of xi,j. The method uses dynamic programming approach to
find Vi,j.. This is a tabulation method and fact is that in O(n^3 ) time the algorithm constructs
the table for all Vi,j to decide whether string x is in L(G).
The method constructs a triangular table shown in Fig. 11.34

Vi,j Vi,1 Vi,2 Vi,3 Vi,4

xi,j

aV1,1

V1,2 = V1,1 * V2,1 V1,1 * V2,2 or

bV2,1 V1,3 = V1,2 * V3,1

V2,2 = V2,1 * V3,1 V1,4

bV3,1

V2,3 =

V2,1 * V3,2 or

V3,2 = V3,1 * V4,1 V2,2 * V4,1

aV4,1

xi,1 xi,2 xi,3 xi,4

Fig. 11.34

R

ST

R

ST