Is WW where W belongs to {a,b}* a context free language?

Sanat Deshpande picture Sanat Deshpande · Mar 5, 2017 · Viewed 7.7k times · Source

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

Answer

Shahar Bental picture Shahar Bental · Mar 5, 2017

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