a^2n b^(2n+1) is a regular language. I am not able to decompose it in xyz so that I can pump any power of y as per pumping lemma. Please help me out.

  • 1
    $\begingroup$ The langauge is not regular. $\endgroup$ – David Richerby Jan 2 '14 at 16:18
  • $\begingroup$ Thanks David.I was attempting MCQ's and came across this question.May be the answer given is wrong. Thanks $\endgroup$ – tarun Jan 2 '14 at 16:25
  • $\begingroup$ Our reference questions may help you sort out misunderstandings. $\endgroup$ – Raphael Jan 3 '14 at 6:36

You probably misunderstood the question. For starters, the pumping lemma can't be used to prove that a language is regular, it can only be used to prove that a language isn't regular. The Wikipedia page for the pumping lemma gives a counterexample.

Secondly, as already pointed out by @DavidRicherby, this particular language is not regular, and as it turns out, you can use the Pumping Lemma to prove this statement.

Roughly speaking, the proof goes as follows:

Assume for the sake of contradiction that the language is regular, and thus, the Pumping Lemma holds. The "y" can take one of three forms:

  1. y contains all "a"s
  2. y contains all "b"s
  3. y is of the form $a^ib^j$ for some $i,j > 0$.

Now, can you see how to derive the contradiction?

| cite | improve this answer | |
  • $\begingroup$ Thanks Dennis.I did it in the same way but the answer was that it is a regular language.So i posted it here because the answer provided by this forum can not be wrong. $\endgroup$ – tarun Jan 3 '14 at 3:15
  • $\begingroup$ @DennisMeng: Thanks, have fun! Your time is much better spent on questions that have not been answered multiple times already. $\endgroup$ – Raphael Jan 3 '14 at 6:45
  • $\begingroup$ True. That last bit will probably just come down to me getting a better idea of what's been repeated over and over here; I'll spend more time just observing to get an idea of what those are. $\endgroup$ – Dennis Meng Jan 3 '14 at 6:48
  • $\begingroup$ @DennisMeng Basically, if it's an exercise from undergrad TCS courses, we've probably got it covered. (We don't have as much non-theory stuff around, unfortunately.) That should not prevent you from answering good questions; these often vary enough (because the included attempts differ) to leave them open. $\endgroup$ – Raphael Jan 3 '14 at 9:43

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