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 (59.9k points)
retagged by | 795 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

+22 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.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
47,913 questions
52,296 answers
67,746 users