The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

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

+6

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

+5

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.

0

@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

0

@Praveen Saini sir can we interpret it like 0^{n} 1^{n} c 0^{n} . 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.

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,530 questions

54,139 answers

187,354 comments

71,068 users