4

Is WW where W belongs to {a,b}* a context free language? If yes, please provide the PDA for it.

1 Answer 1

14

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:

  1. |vwx|<=p
  2. |vx|>=1
  3. uv^n wx^n y is in the language for any positive n

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

3
  • " 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, 2020 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 Mar 29, 2020 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, 2020 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.