0
1.6kviews
Show that the following languages are not context free
1 Answer
0
9views

(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.

Please log in to add an answer.