Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 329

or V1,2 * V3,2 = {S} * {S} = {SS} we find nothing.

or V1,3 * V4,1 = {B} * {A, X} and find nothing.

Therefore, V1,4 = {S} (∴ S ⇒ XB}

This entry is shown in Fourth column of table shown in Fig. 11.35.

Conclusion

From the table (Fig. 11.35) we see that its last column contains the nonterminal/s that derived
the complete string x. If this column contains the start symbol S it means,

S ⇒N x

Then, string x ∈ L(G).

Conversely, if start symbol S ∉ V1,n (last column) then x ∉ L (G).

CYK Algorithm

Start with the CNF grammar G = (VN, VT, S, P), and assume that string x is of length n(| x |

= n).

begin

For i = 1 to n do // for all substring of length 1

Vi,1 = {α ∈ VN | A → xi,1 is a production in G}

End for (i)

For i = 2 to n do // for all substring of length 2

For j = 1 to n-i+1 do

Vj,i = ∅

For k = 1 to i-1 do

Vj,i = Vj,i ∪ {A ∈ VN A → BC is a production in G and B ∈ Vj,k

and C ∈ Vj+k, i–k}

End for (k)

End for (j)

End for (i)

If S ∈ Vi,1 then x ∈ L(G) otherwise x ∉ L(G)

end

So, the algorithm must terminate with in the time complexity O(n^3 ) due to nested three

for loops with variables k, j and i.

[In general the compiler of ‘C’ and ‘PASCAL’ languages are of linear time complexity i.e.

O(n).]

11.15 UNDECIDED PROBLEMS (UDP) OF CONTEXT FREE LANGUAGES

There are a lot more problems of the context free languages (CFLs) that have no known solution,

such problems are called undecidable problems. For example, following problems for CFGs/

CFLs have no algorithms, i.e.,

l Problem of equivalence

Remember, problem of equivalence is decidable for regular languages that says that if L 1 and
L 2 are two regular languages then they are equivalence if and only if,
(L 1 – L 2 ) ∪ (L 2 – L 1 ) = ∅