# Determining if language is context free

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?

-

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

-
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