3

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.

Cleb
  • 25,102
  • 20
  • 116
  • 151
Mint.K
  • 849
  • 1
  • 11
  • 27
  • I'm voting to close this question as off-topic because it belongs to math.stackexchange.com or http://cs.stackexchange.com/ – timgeb Feb 28 '16 at 00:19
  • @timgeb, it most certainly doesn't belong on math exchange. You could argue for CS but not math IMHO. This is about formal languages. – ChiefTwoPencils Feb 28 '16 at 00:20
  • @ChiefTwoPencils So what? It's still a mathematical proof we're talking about here. The line between theoretical computerscience and math is very blurry. Do you really want to put it on http://linguistics.stackexchange.com/ ? – timgeb Feb 28 '16 at 00:22
  • No, I already suggested the alternative location if appropriate. This book, topic, and problem is not *based* in mathematics despite it being a "mathematical" proof. It's based in computational theory and is a standard course in a computer science curriculum. One would have to understand the rules to prove this; rules not likely taught to mathematicians (just a guess tho). @timgeb – ChiefTwoPencils Feb 28 '16 at 00:26

1 Answers1

2

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.

ChiefTwoPencils
  • 13,548
  • 8
  • 49
  • 75
  • Let k = 0, and m = 3. Then it's aaaaaa aaaaaa. I set x = a, y = aa in the first 6 a's, and z the rest. If I pump y 0 times. The string becomes aaaa aaaaaa. Which is not equal to ww^R. First w has 2 less a's. Am I doing something wrong? – Mint.K Feb 28 '16 at 02:22
  • @M.Kim, I think your problem might be who's choosing what. Refer to (3) in example 4.7 on 117. The opponent chooses *m* and the decomposition *xyz*. You pick *w* before I pick the decomp. Also, yes, we had an even total of a's and took an even number of them away. We still have an even number of a's. We're not talking about "sides"; we're interested in the string being in *L* or not. – ChiefTwoPencils Feb 28 '16 at 02:35
  • @M.Kim, that's why using (a^m)(b^m) is so easy. (a^m)(b^m)(b^m)(a^m) *can* be looked at as "sides" since we're only allowing them to deal with the a's on the one side (sides being separated by the b's). So, if I add or remove any a's it fails the assumption because I can't make up for it on the other end (I'd have (a^(m-k))(b^2m)(a^m) : (m - k) < m). Not true when you make it so easy with a single symbol and an even number of total symbols. Does that help at all? – ChiefTwoPencils Feb 28 '16 at 02:48
  • yes that helps and I understand that it keeps generating an even amount of a's. However, length-wise, both "sides" have to be the same although they might contain all even number of a's. Since L = ww^R, |w| and |w^R| have to be the same, right? But if i take even amount of a's(y) on the left side, how is that string still in L? – Mint.K Feb 28 '16 at 03:36
  • @M.Kim, I don't see that constraint. It's been awhile but I think you're being too strict. In the book - the chosen w = w(w^R) = xyz = (a^m)(b^2m)(a^m) so we look at the total string. We choose any w in L and want to see if *any* w(i) is in L. So, instead of viewing your example where i=0 as aaaa aaaaaa, look at it as aaaaaaaaaa which is in L. – ChiefTwoPencils Feb 28 '16 at 03:53
  • yes now i get it. I was too strict on looking at it as "sides" . Looking at it as a whole string definitely makes sense. Thanks – Mint.K Feb 28 '16 at 04:16
  • @M.Kim. Glad to help. Doesn't help that the proof has you choose a "w" that isn't the same w in that language definition. – ChiefTwoPencils Feb 28 '16 at 04:22