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!

Answer 1

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:

• x=a^k
• y=a^l
• z=a^2p-k-l b^p

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

Taking i=2, you have xy²z:

• s = a^k a^la^l a^2p-k-l b^p

that is:

• s = a^2p+l b^p

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