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^k b^3l a^l | k ≥ 1 , l ≥ 0}

I have decided to choose w = a b^3p a^p, then |w| = 4p+1 ≥ p

Any tips?

Thank you!

Answer 1

I am not sure about the exact formulation of the pumping lemma that you are using. At any rate, this is a rather tricky case, because standard formulations like in wikipedia only let you pump somewhere in a prefix of fixed length. But your initial block of a allows pumping anywhere and can be arbitrarily long. Thus you have to use some additional property. I suggest two:

• Regular languages are closed under reversal. Thus you may as well look at $L^R = {a^l b^{3l} a^k}$. Now any pumping in the initial block of a will lead out of the language.
• Regular languages are closed under intersection. If you take the intersection with a b+ a+ you end up with ${a b^{3l} a^k}$, and now pumping in the b block will take you out of the language.