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 RicherbyJan 2, 2014 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$– tarunJan 2, 2014 at 16:25
-
$\begingroup$ Our reference questions may help you sort out misunderstandings. $\endgroup$– RaphaelJan 3, 2014 at 6:36
1 Answer
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:
- y contains all "a"s
- y contains all "b"s
- 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$– tarunJan 3, 2014 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$– RaphaelJan 3, 2014 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$ Jan 3, 2014 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$– RaphaelJan 3, 2014 at 9:43