If I let string w
be a^mb^m
then we know that y
will consists of only a
's because of the rule |xy| <= m
.
And if I set i=0
, then ww^R
will have fewer a
's on the left side than on the right side. Thus, it proves that this language is not regular.
However, my text book (An Introduction to Formal Languages and Automata pg. 118 by Linz) says if I were to choose w = a^2m
and let y = aa
, then I would fail.
But how so?
To my mind, no matter what x
, y
, z
are, the first a^2m
will have fewer a
's or more depending on what i
is than the second a^2m
.
The reason why is you have an even scalar on m. Since the strings in L are just a string's reverse appended to itself, an even number of a's will always be in L.
For any m >= 1 you have aa[aa...]. So, when your opponent selects y = aa, they force you to inject a string that is in L into w(i). No matter how many times, if at all, it's pumped you end up with: (aa)^k : k = pumps, which is a string in L
I think it's a bad choice to only use a. Having two alphabet symbols usually makes it easier to win. As the book continues to say, you can't assume it should be easy to beat your opponent; any attempts are automatically invalid.