Question

Prove that the language consisting of all the words that have equal number of a's and c's and exactly twice as many b's is not context-free.

Answer 1

The language is not context free. This can be proved by pumping lemma as follows:

Consider a string z that belongs to the above language(L) such that length of string z, |z| >= n.

One such z will be aⁿcⁿb²ⁿ.

If this language were context free, then by pumping lemma, it should be possible to find u,v,w,x,y such that :

z = uvwxy and

(1) |vwx| ≤ n
(2) |vx| ≥ 1
(3) for all i ≥ 0: uvⁱwxⁱy ∈ L

i.e., we must be able to pump v and x any number of times(including 0 times) and still the resulting string must be in the given language.

Now let's look at the possibilities for vwx.

vwx cannot contain all of a, c and b as the length of vwx is less than or equal to n. Thus following cases are possible for vwx.

i) vwx contains a and c. Then for i=0: uv⁰wx⁰y = uwy. Since the length of vx is greater than or equal to 1, this essentially decreases the total number of a's or c's in the string, however the number of b's remains the same. This means that total number of b's will not be twice the number of a's or c's. Thus, the resulting string is not in L.

ii) vwx contains c and b. Then again for i=0  uv⁰wx⁰y = uwy. Again the number of b's or c's decreases but number of a's remains the same. Again the resulting string will not be in L.[Number of c's decreases - it is not equal to n, Number of b's decreases: b's will be less than twice the number of a's]

iii) vwx consists of only either a's or b's or c's. Then for i=0: uv⁰wx⁰y = uwy. In this case number of one of either a's or b's or c's will decrease while others will remain same which will violate the property of strings in L.

Thus, it can be seen that in either case, it is impossible to find a combination of u,v,w,x,y that satisfies pumping lemma.

Hence, we have found a string in L with length greater than or equal to n but does not satisfy pumping lemma. So, the language is not context free.