edited by
479 views

1 Answer

3 votes
3 votes

Suppose, $L$ is context-free language. Now, Pumping lemma for CFL says:

$\exists n$ such that  $\forall z \in L$ with $|z| \geq n,$ 

$\exists z$ such that $z=uvtxy$ with

  1. $|vtx| \leq n$
  2. $|vx| >0$
  3. $\forall i \geq 0, uv^itx^iy \in L$ 

Now, consider an element of  set $L$ as $z= aba^nbab^n$

Here, $z \in L$ and $|z| \geq n$

Now, try to decompose $z$ as $z=uvtxy = aba a^2a^{n-3}bab^n$ with

$u = aba, v = a^2, t = a^{n-3},x=b,y=ab^n$ 

Here, we can see $|vtx| \leq n$ and $|vx| >0$

Now, pump this string two times i.e. for $i=2, uv^itx^iy$ is:

$uv^2tx^2y = abaa^4a^{n-3}b^2ab^n = aba^{n-2}b^2ab^n$ which is not in $L$ but according to pumping lemma, it should be in $L.$ So, Contradiction. So, what we have assumed is incorrect and  hence, $L$ is not a context-free language. 

Related questions

0 votes
0 votes
1 answer
1
srestha asked Apr 19, 2019
651 views
How by Pumping Lemma we can prove that“context free grammar generate an infinite number of strings”and here what could be pumping length ?
0 votes
0 votes
0 answers
4
Sumit Singh Chauhan asked Aug 15, 2018
273 views
The logic of pumping leema is good example of The Pigeon Hole Principle. Can anyone please explain this?