# How to handle multiple exponents (Pumping-Lemma)

Example $$L = {(ab)^na^k|n\ge k}$$

When searching for a word $$w$$, using $$p \in \mathbb{N}$$, for instance $$(ab)^pa^p$$, but wanting to pump $$a$$ (which is not possible because $$|xy| \le p$$ holds), how do I deal with that? I would need a variable $$j \lt p$$ for $$(ab)^ja^j$$ to have the possibility that $$a \in y$$, so I can pump $$a$$ and argue that $$(ab)^ja^{j+(i-1)|y|} \notin L$$ → The condition is no longer satisfied: $$\forall i\ge 0: xy^iz \in L$$.

My question: How is the best way to handle multiple exponents? Not just in this but in general.

• It would be a nice exercise to pump down with $i=0$, and consider all possibilities of $y$. Feb 13 at 19:52

There is actually a more generalized version of the pumping lemma, where you can pump a substring anywhere in the word. The proof is almost the same: in a computation of a word $$w$$ in a DFA, if there is a substring long enough, it contains a cycle.

The lemma can be stated as such:

Let $$L$$ be a regular language over alphabet $$\Sigma$$. Then there exists a pumping length $$p$$ such that if $$uvw\in L$$ with $$|v| \geqslant p$$, then there exists a decomposition $$v = xyz$$ such that:

• $$|xy|\leqslant p$$
• $$y \neq \varepsilon$$
• for any $$k\in \mathbb{N}$$, $$uxy^kzw\in L$$.

For your language, you want to apply this lemma with $$uvw = (ab)^pa^p$$ with $$u = (ab)^p$$, $$v = a^p$$ and $$w = \varepsilon$$.

There is another way to handle this language without the need of changing the lemma, but you need a bit of a trick: you can show that $$L$$ is the mirror language of $$L' = \{a^k(ba)^n\mid n\geqslant k\}$$. You can use the classic version of the pumping lemma to show that $$L'$$ is not regular, and since the mirror operation must preserve regularity, $$L$$ is not regular either.

• Thank you, especially getting creative with the mirror language $L'$. Helped me a lot! Feb 13 at 11:12

There is a solution to your pumping problem using the classical formulation of the Pumping Lemma, writing $$w=xyz$$ and considering $$|xy| \le p$$ and $$xy^iz$$ for $$i\ge 0$$. The trick is pumping down...

For clarity, instead consider $$L = \{b^na^k \mid n\ge k\}$$. Assume pumping length $$p$$. Consider the string $$w = b^pa^p$$. Setting $$w = xyz$$ with $$|xy|\le p$$ implies that $$y$$ consists of $$a$$'s only. Deleting $$y$$, i.e. setting $$i=0$$, gives us the string $$xy^0 z = a^{p-|y|} a^p$$ which is not in $$L$$ as $$p-|y| < p$$.

In general there might not be a common solution for handling "multiple exponents". An infamous example is the language $$\{ a^n b^m \mid n\neq m \}$$ where the usual Pumping Lemma can be applied, but one needs factorials. See https://cs.stackexchange.com/a/64074/4287. Other approaches are available too, see the other answers to that problem.