How to prove $\{a^nb^na^n \mid n\geq1\}$ is not regular using pumping Lemma

Question

Here the problem is that I’m confused how to take the pumping value $p$ is it arbitrary any value?

Also I don’t know if I should prove all $3$ conditions of the pumping lemma is false or if any one should be proved as false by considering the given language as regular by proof by contradiction.

Answer 1

Let's recall the Pumping Lemma statement:

For all regular language $ L $, exists a positive constant called $ p $ (i.e. $ p \geq 1 $) such that every string $ w $ in $ L $ with length $ |w| \geq p $ exist strings $ x, y, z $ such that $ w = xyz $ and that statisfying the following conditions:

• $ |y| \geq 1 $
• $ |xy| \leq p $
• $ xy^iz \in L, \: \forall i \geq 0 $

So yes, $ p $ is an arbitrary value and a fixed costant, called "pumping length". The proof for your language may be the following:

Let's assume that $ L $ is a regular language, so for all strings $ w \in L $ it must satisfy conditions of PL. Now choose a string $ w $ that is in $ L $, let choose $ w = a^pb^pa^p $ and we can split $ w $ in $ xyz $, so let's say that:

• $ x = a^k $
• $ y = a^h $
• $ z = a^{p-h-k}b^pa^p $

with $ h \geq 1 $ and $ h + k \leq p $.

Now note that the first two conditions of the PL are satisfied, but for the third, if we take $ i = 0 $ then $ w = xy^0z = a^ka^{p-h-k}b^pa^p = a^{p-h}b^pa^p $ and this string clearly doesn't belongs to $ L $ and this contraddict the initial assumption of $ L $ regular, so this meanings that $ L $ isn't a regular language because it doesn't satisfy the PL.