2
$\begingroup$

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.

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you, especially getting creative with the mirror language $L'$. Helped me a lot! $\endgroup$
    – Robert
    Feb 13 at 11:12
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.