formal-languagescontext-free-language

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


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


Solution

  • 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