0
$\begingroup$

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?

1 Answers 1

1

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

  • 0
    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.2012-05-30
  • 0
    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?2012-05-30
  • 0
    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.2012-05-30
  • 0
    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.2012-05-30
  • 0
    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?2012-05-30
  • 0
    No, you have to show that all cases fail.2012-05-30
  • 0
    Ahhhh, I just had an "ahha" moment with your last comment!2012-05-30
  • 0
    Glad to hear it. :)2012-05-30