Tips to proof a language is not regular using Pumping Lemma

Question

I am trying to prove that the following language is not regular using the pumping lemma

L = {aⁱ b^j | i = 2j for some j ≥ 0}

I have decided to choose s = a^2p b^p, in this way |s| ≥ p and I can split it in three pieces xyz where for every i ≥ 0, xyⁱz ∈ L.

Any tips for continuing the proof?

Thanks!

Apply the lemma! you're almost done. You know that the lemma holds, so there exist such xy'z , choose i+1, show that the word is not in the language so the language is not regular. — Benjamin Gruenbaum, May 23 '13 at 11:02
One of the conditions of the pumping lemma says that |xy| <= p. In this case p < 2p so |y| < 2p. If I chose i = 2, the string would be xyyz. The length is |xyyz| = |xyz| + |y| < 2p+p + p. So the number of a's can't be twice the number of b's. Is it correct? — colis, May 23 '13 at 11:43
Right, just explain why the number of _a_s can't be twice as much as the number of _b_s and you're done — Benjamin Gruenbaum, May 23 '13 at 11:46
@colis read my [this answer](http://stackoverflow.com/questions/15174070/is-l-an-bm-nm-a-regular-or-irregular-language/15184740#15184740) and [this answer](http://stackoverflow.com/questions/14705091/pumping-lemma-for-regular-language/14708650#14708650) In which I have explained that in pumping lemma we don't know where looping part so you need to break strings in `L` in all possible ways. And If still its a problem let me know. — Grijesh Chauhan, May 24 '13 at 15:31

score 1 · Answer 1 · answered Feb 27 '14 at 14:57

Choose s = a^2p b^p is right!

As said by Grijesh Chauhan we must break strings in L in all possible ways.

So you can split s in:

where |xy|≥ 0 and |y|>0.

Taking i=2, you have xy²z:

that is:

Since l contains at least one 'a' (because |y|>0). You can say L is not regular

1 Answers1