The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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$.
asked in Theory of Computation by Veteran (52k points)
retagged by | 862 views
C is not a string ... it is just a symbol ... so we cant extend c as we like and so this is not a CFL (and so not regular)....

2 Answers

+3 votes
Best answer

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. 

answered by Boss (24.9k points)
selected by
+22 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 .

answered by Veteran (55.8k points)
edited by

I got the point. We can do like this: 

First, whatever is left of c we put it onto the stack 1.
Now, once we observed c, we pop every element (one by one) from stack 1 and push it to stack 2.
And now, we will match the right of c with the top of the stack 2.

using pumping lemma

let xcx=uvwyz , v be in left x , w=c and y be in right x.

now pumping v and y will not give a string of the form xcx.

eg- 0100c0100=uvwyz where u=01, v=00, w=c, y=01, z=00

now pumping v and y gives uv^2wy^2z= 010000c010100 which is not in the form of xcx

Hi , Can we think about in this way.

Let the string be 1100c1100=wcW

So first part we put in a stackA(1100). So at the bottom of the stackA, it  has the 1 at the bottom and the top we have 0. Then c is pushed into StackA. Once the PDA sees the symbol 'c', it will start popping the topmost terminal if it finds the same symbol as next input.

But  the next immediate input symbol is 1  (1100) and top of stackA is 0. So it can't do pop operations.

So the next (1100) we have to put into another stackB . So stackB has  1 at bottom and 0 at top. 

Now pop 'o' (top most)from stackB and push it to stackA. Stack A has the top most symbol '0' and seeing '0' as an next input symbol which is coming from stackB,, the action would be remove the top element from stackA.

And this process will continue until we empty the stackB which will also ensure empty of StackA.

The main purpose of taking the StackB is to reverse the second part of strings. So that we can push the second part of the string in reverse order to StackA whatever we have pushed in first part.

That's why we find WcW(r) is context free as we need only one stack. Here second part is already reversed.

However wcW is context sensitive as for the second part we need to reverse which needs an additional stack. So it is not context free.

Absolutely Correct :)
@hemant if in the left of c, 011 is the string then in the right also 011 will be the string ,only 01 is not possible because language is xcx
@abhijeet sen nice approach bro

@Praveen Saini sir can we interpret it like 0n 1n c 0n . now equal no of 0s and 1s to the left of c will be counted successfully but now we don't have count in our stack to count equal number of 0s to the right of c.

@Hemant it can be done with the queue as we have to compare from start and queue can be implemented with help of two stacks.
Good approach

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,530 questions
54,139 answers
71,068 users