in Theory of Computation edited by
474 views
0 votes
0 votes

$L=\{wa^nw^Rb^n\mid w\in \left \{ a,b \right \}^\ast ,n\geqslant 0\}$

Can anyone give me step by step solution that shows this is not CFL by pumping Lemma?

in Theory of Computation edited by
by
474 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. 

2 Comments

What should be the value of n? you have not taken any value here

Also why did you take a^n-3 ?

Other steps I understood except for the pumping length. Can you explain how to take that?
0
0

$n$ is an integer which is also called as pumping length and $n \geq 1.$ I have taken $a^{n-3}$ so that I can decompose $z$ in $u,v,t,x,y$ such that resultant string after pumping will not be in $L$ and prove that it is not a CFL.  This is not the only way. You can consider other strings also and decompose intelligently so that after pumping up, you get a string which is not in L. 

You can get the idea from here. Though this pumping lemma is for regular languages but the idea is same.

0
0

Related questions