The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 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$.

+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 .

+5

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.

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.

0

ok so in ndpda we maintain 2 copies of same stack rght?e.g pda for the language ww^{R.}

^{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?}

+1

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

Here c is center.

+1

yes u r right.

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

+1

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

0

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.

+3

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.

+1

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

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

+2

Hi , Can we think about in this way.

Let the string be **1100**c*1100**= 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 **W**cW(r) is context free as we need only one stack. Here second part is already reversed.

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,996 questions

45,492 answers

131,517 comments

48,591 users