in Theory of Computation
1,381 views
2 votes
2 votes
Let $B$ be the language of all palindromes over $\{0,1\}$ containing equal numbers of $0's$ and $1's.$ Show that $B$ is not context free$.$
in Theory of Computation
by
1.4k views

1 Answer

3 votes
3 votes

Pumping lemma for CFLs:

Let $L$ be a CFL. Then there exists some integer constant $P \geq 1$ (Called Pumping length or pumping-lemma constant)  such that if $w ∈ L$ with $|w| ≥ P,$ then we can write $w = uvxyz,$ subject to the following conditions:

1. $|vxy| ≤ P.$

2. $vy \neq \in .$

3. For all $i ≥ 0,$ we have $uv^ixy^iz ∈ L.$

i.e. Informally, For every sufficiently large string $w$ in $L,$ We must be able to split it such that it is possible to find at most two short, nearby substrings that we can “pump” $i$ times in tandem, for any non-negative integer $i,$ and the resulting string will still be in that language.  

So, In the Whole String $w$ with $|w| \geq P,$ "Anywhere in this string", "Within At Most $P$ symbols", We must find Two sub-strings(Possibly empty, Not Both Though) such that we can "Pump" both of these sub-strings $i \geq 0$ times in tandem i.e. Both repeated $i \geq 0$ times.


Now, Assume that Given $L$ is CFL, Hence, It will satisfy Pumping lemma for CFL.

So, There must be some positive integer constant (pumping length) $\geq1$ existing for this language. Let it be $P.$

So, Now for every string $w \in L$ whose length is greater than or equal to $P,$ we must have some partition $uvxyz$ satisfying all the above conditions.

So, Let me take the string $1^{P} 0^{P}0^P1^{P} \in L$, Now Try to split it into five parts $uvxyz$ such that All the Three conditions of pumping lemma must satisfy.

Basically in Pumping lemma for CFL, You want to find $"$at most $P"$ consecutive symbols in the String(anywhere in the String) such that you can find two short sub-strings in that part and Pump those sub-strings in tandem. 

But for the above String  $1^{P} 0^{P}0^P1^{P}$, we cannot find any such at most $P$ consecutive symbols anywhere in the string which will satisfy the Pumping lemma conditions. (Hint : Check different possibilities i.e. Take Those at most $P$ consecutive symbols  completely in $1^P$ part or completely in $0^P$ part  or some in $1^P$ part and some in $0^P$ part or some in $0^P$ part and some in $1^P$ part   of the string .. etc.. covering all possible partitions..  )

When you take $vxy$ substring completely in $1^P$ part and however you choose $v,y$ in this part, one thing is certain that when you repeat $v,y$ Zero Times then at least one 1 will be removed from the string and hence the resulting string will not belong to the language because number of 0's and number of 1's will not remain the same. Similar logic applies for when you take $vxy$ substring completely in $0^P$ part.

When you take $vxy$ substring between $1's $ and $0's$,  however you choose $v,y$ in this part, one thing is certain that when you repeat $v,y$ Zero Times then at least one 1 and at least one 0 will be removed from the string and hence the resulting string will not belong to the language because it won't be a palindrom. 

So, Given language doesn't satisfy Pumping lemma and hence, $L$ is Not CFL.


For more examples to understand Pumping lemma, I have answered many Questions based on Pumping lemma and You can refer to them in my profile under "All Answers" tab.


$\color{Red}{\text{Understand Complete Pumping Lemma for Regular Languages, Crystal Clear:}}$

Here is Complete Pumping Lemma Lecture: https://youtu.be/8cdPjuYbIrU 

This Pumping Lemma lecture contains EVERYTHING about Pumping Lemma of Regular Languages, i.e. Proof, Examples, Variations, GATE PYQs, Finding minimum pumping length etc. Watch this lecture for Complete, Correct & Clear Understanding.

edited by

Related questions