retagged by
5,009 views
34 votes
34 votes
Show that the language $$L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$$ is not context free. $c$ is not $0$ or $1$.
retagged by

2 Answers

Best answer
37 votes
37 votes

We can prove that the given language $L$ is Not CFL using the "Pumping lemma for CFLs". That is formal and correct way to prove this. Since this Question is subjective, and that year GATE was a subjective exam, so All other answers which give some vague informal idea (I have written that informal idea at the end of the answer) behind $L$ being Non-CFL would have been awarded zero marks as that doesn't prove anything.  


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}c1^P0^{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}c1^P0^{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 $0^P$ part and some in $1^P$ part or some in $1^P$ part and some in $0^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 the substring to the left and right of $c$ 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 the substring to the left and right of $c$ will not remain the same.

So, Given language doesn't satisfy Pumping lemma and hence the contradiction. So, $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.


The Informal idea behind $L$ being Non-CFL is that in PDA, we have a Stack as an auxiliary memory. And Stack works in LIFO manner. Since we have the language as $w_1cw_2$So, if you want to match the substring to the left of $c$ i.e. $w_1$ with that of to the right of $c $ i.e. $w_2,$ You need to PUSH left substring $w_1$ into the stack and skip $c$ and now You need to match the first symbol  of $w_2$ with the first symbol of $w_1$ But the first symbol of $w_1$ is at the bottom of the Stack. So, that's the problem with Stack. Hence, we can informally say that Forward matching cannot be done by Stack or for that matter by PDA. 


$\color{Red}{\text{Understand Complete Pumping Lemma of 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
30 votes
30 votes

Language contains strings where sub string on left of $c$ is same as that on right of $c$ 

say $01100c01100$

sub string on left of $c$ and right of $c$ cannot be matched with one Stack 

while that can be done using two stack

if we push all $0$'s and $1$'s on left of $c$ in stack $1$ , and all $0$'s and $1$' on right of $c$ in stack $2$ 

then Top of stack  of both stack will have same symbol. That can be matched .

edited by

Related questions

13 votes
13 votes
3 answers
1
Kathleen asked Sep 23, 2014
2,350 views
Show that the formula $\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right]$ is not a tautology.Let $A$ be a tautology and $B$ any other formula. Prove that $(A \ve...
20 votes
20 votes
3 answers
3
Kathleen asked Sep 23, 2014
7,344 views
Context-free languages are closed under:Union, intersectionUnion, Kleene closureIntersection, complementComplement, Kleene closure