The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 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 (59.6k points)
retagged by | 616 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)....

1 Answer

+20 votes
Best answer

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.1k points)
edited by
since multiple stack is used ,isnt it a ndpda? hence ndcfl
Since multiple stack is used,isn't it a NDPDA which is NCFL ..plz clarify my doubt sir
PDA is all about single stack, NPDA or DPDA.

if more than one stack required , then language is not CFL, cannot be implement by PDA .

PDA by default single stack PDA is for cfl.

ok so in ndpda we maintain 2 copies of same stack rght?e.g pda for the language wwR.

since here we are not sure about the center marker as in wcwR as to till when to push nd when to strt matching nd popping.,we need 2 flows.m i correct Sir?


Deterministic or non deterministic depend on transitions (as in FA),  not on stack or copies of stack. 

Here c is center. 

so what language is this?
it is csl @BILLY

To prove, we have to use pumping lemma of CFL, right ?

Or any other way?


yes u r right.

The pumping lemma for cfl is often used to prove that a given language L is non-context-free.

I personally never use pumping lemma to proof any language. I just count the no. of stacks.. like sir have done here.

I did not understand the last point.

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 

Suppose on the left of c we have 011 and right of c we have 01. Then both stack will have the top symbol as 1. But this is not present in the language.


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

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

41,146 questions
47,708 answers
62,405 users