Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is {xayb : x,y in {a,b}* and |x|=|y|} a context free language? My natural instinct would be to say that the answer is no, but can someone show me how to prove this?

share|cite|improve this question
up vote 1 down vote accepted

It is context free; $|x| = |y|$ is not a very stringent requirement.

share|cite|improve this answer
and I'll be happy to provide a grammar if you want one, but I find that often students can figure it out once they are told what the answer is. Which is, of course, why it's a good exercise to learn to figure out the answer on your own, because that's the hard part. – Dustan Levenstein May 30 '12 at 12:03
I guess, my issue is that I tend to use the pumping lemma a little too leniently and try pounding a square peg in a round hole with it. I think of the string z=({a,b}^m)a({a,b}^m)b and then think that okay, if z=rstuv, |stu|<=m, and |su|>1, then I think the pumping lemma states that z=({a,b}^m+1)a({a,b}^m)b would also be in L which isn't true. Does that make sense? – Jack Kobil May 30 '12 at 12:08
too leniently indeed! Two things to keep in mind: 1. Note that you are assuming that $|su|$ is just one character in the first portion of the expression. It may be multiple characters, and it may cross regions. 2. Although you correctly state that $\{a,b\}^{m+1} a \{a,b\}^m b$ is not in $L$, I'm not convinced you thought that through. I say it's not in $L$ because every word in $L$ is of even length. You're probably looking at the form of the word, and saying it doesn't match that given. The same word can be broken down in many ways. – Dustan Levenstein May 30 '12 at 12:14
And to show that it pumps: let $s$ be one character in the first region $\{a,b,\}^m$, and $u$ be a character in the third region. Then pumping in or out preserves $|x| = |y|$, leaving the required $a$ and $b$ interspersed untouched. – Dustan Levenstein May 30 '12 at 12:16
Yes, I based that on the assumption that it |su| was just in the first portion of the expression. but doesn't it only take one counter example to prove that it has a contradiction? – Jack Kobil May 30 '12 at 12:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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