0
Show that the following languages are not context free

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2014

0
0

(i) $L = (0^i1^j2^i3^j | i \gt= 0,j \gt= 1)$

Let L be context free

Therefore, by Pumping Lemma

| y | > 0, | xy | <= p

Where p is an integer such that | s | >= p

Let $y = 1^j \ and \ x = 0^i \ and \ z = 2^i3^j$

Therefore, | x | = i,| xy | = i + j and | z | = i + j

But | xy | >= p

Hence, there arise two cases

Case 1: If | xy |= p then

i + j = p

ifi = 0, j = p ….………….(1)

Case 2: If | xy |< p

i + j < p

If i = 0,then j < p

Hence, a tentative value for p can only be found if i = 0, not for other values of I as we would not understand whether it would take case 1 or case 2.

ii) $L = {SS^T | S Σ (a,b)*}$

We assume a value for L such as

L = bbabaababb

Let x = bbab, y = aa and z = babb

Therefore, | x | = 4,| y | = 2 and | z | = 4

Therefore, by Pumping Lemma, there exists a ‘p’ such that

| y | > 0 and | xy | <= p

But | xy | = 2 + 4 = 6(in this example)

| xy | = X + 2 (in general) ……………………(1)

Hence, two cases arise out

Case 1: | xy | = p

Therefore, p = 6

Case 2: | xy | < p

Therefore, p > 6

So in general, value of p would depend on number of occurrences the x-part of the string

Hence, the language can be generated by a context free grammar without needing to worry about the value for p.

Hence, the language maybe be context free or some other type of language.

0