Is WW where W belongs to {a,b}* a context free language? If yes, please provide the PDA for it.
1 Answers
No, it is not
Assume, for sake of contradiction, that it is, then there is a PDA that accept it.
According to the pumping lemma (for CFGs), there is a length p
such that for every word (we will pick one shortly) s
there are some substring u,v,w,x,y
such that s=uvwxy
and:
|vwx|<=p
|vx|>=1
uv^n wx^n y
is in the language for any positiven
Let's consider the word a^p b^p a^p b^p
, and such u,v,w,x,y
Either vwx
contains the middle of the word, or it's entirely contained in the first half, or it is entirely contained in the second half.
If it's in the first half, then in the word uv^2 wx^2 y
. We have added a total length of no more than p
, thus we have "moved" the mid-point by no more than p/2
, so right now the mid-point continues with b
, but the word starts with a a
, so it's not of the form ww
Same argument goes for it being in the second half.
Now let's assume it contains the middle, and consider uwy
(using n=0
). Since |vwx|<=p
, then we have removed from the a's and b's in the middle, but not from the a's and b's at the edges. We have also removed a positive amount of letters, so uwy
is of the form a^p b^k a^m b^p
were either k<p
or m<p
. Eitherway, it's not of the form of ww

- 991
- 6
- 16
-
" We have added a total length of no more than p, thus we have "moved" the mid-point by no more than p/2". Can you elaborate on this part? Thank you. – lmngn23 Mar 28 '20 at 17:50
-
We've added to the original word v and x, and we have `|vx|<=|vwx|<=p`, so overall the total length was increased by no more than `p`. The middle is shifted by half of that, so no more than `p/2` – Shahar Bental Mar 29 '20 at 18:17
-
This is a good example for using pumping lemma where the details of s actually matter except for it being in L. Nice answer sir! – yooloobooy Jun 12 '20 at 21:28