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.


closed as unclear what you're asking by Raphael Jan 3 '14 at 6:37

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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?

  • $\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.