Can I prove, using Pumping Lemma, that $L=\{ a^i b^j a^j b^k | i,j,k \ge 1 \}$ is not a regular language?

Question

By pumping lemma, we have that for each sufficiently large $z \in L$, there exists $u, v$ and $w$ such as $z=uvw$, whith $|uv| \leq p$, $|v| \ge 1$ and $uv^iw \in L$, for each $i \ge 0.$ ($p$ is the threshold given by PL)

When I want to find a word that doesn't respect the PL, it must have some $a$-s as a prefix, because $k >0$. Given this impediment, I can not prove that any decomposition $u, v, w$ gives me a contradiction, because there is always the possibility that $uv = a^j$ for some $j$ and this keeps $uv^i w$ in $L$.

What can I do? Can I use some closure properties of regular languages?

It works with proving that only the second part of the words is not regular and this will imply that the concatenation is also not regular?

I know that with Myhill-Nerode theorem the problem is solved in no time, but I must use PL.

Answer 1

As you've observed, the language $L=\{ a^i b^j a^j b^k | i,j,k \ge 1 \}$ is pumpable even though it isn't regular. Thus, you cannot show its non-regularity using only the standard pumping lemma for regular languages.

The statement above is incorrect, as shown by vow lacks forte's answer. In particular, for any proposed pumping length $p$, the word $a b^p a^p b \in L$ is not pumpable; the critical observation is that repeating any non-empty substring of the first $p$ symbols zero times will result in a word that is not in $L$. I would delete this answer, but I cannot as it has been accepted.

The is, however, a generalized version of the pumping lemma (which Wikipedia cites to Savitch (1982), Abstract Machines and Grammars, p. 49) that basically shows that not only is every sufficiently long word in a regular language pumpable, but so is every sufficiently long substring of such a word.

More formally, this generalized pumping lemma states that every regular language $L$ has a generalized pumping length $p \ge 1$ such that, for any word $uwv \in L$ consisting of an arbitrary prefix $u$ and suffix $v$ separated by a midpart $w$ of at least $p$ symbols, the midpart $w$ can be further divided up as $w = xyz$, where $|xy| \le p$ and $y$ is non-empty, so that $uxy^izv \in L$ for every $i \ge 0$.

This generalized pumping lemma is sufficiently strong to prove that your language $L$ is not regular. In particular, if your language $L$ was regular, it would have some generalized pumping length $p \ge 1$. But then we could choose e.g. $u = a$, $w = b^p$ and $v = a^pb$, yielding a word $uwv \in L$ that contains a non-pumpable substring $w = b^p$ of length $p$, and thus a contradiction.

Answer 2

If $p$ is a proposed pumping length, consider the string $$w = \mathsf{a}\mathsf{b}^p\mathsf{a}^p\mathsf{b}.$$ (That is, $i = 1$, $j = p$, $k = 1$ from the definition of $L$.) Suppose that $w = xyz$ is a decomposition of this string so that

1. $|y| \geq 1$,
2. $|xy| \leq p$, and
3. $xy^\ell z \in L$ for all $\ell \geq 0$.

Note that $xy = \mathsf{a}\mathbf{b}^q$ for some $0 \leq q < p$. We just go through the cases.

• If $x = \varepsilon$ and $q = 0$ (so that $xy = y = \mathsf{a}$), then $xy^0z = xz = \mathsf{b}^p\mathsf{a}^p\mathsf{b} \notin L$. (All strings in $L$ begin with an $\mathsf{a}$.)
• If $x = \varepsilon$ and $q > 0$ (so that $y = \mathsf{a}\mathsf{b}^q$), then $xy^2z = \mathsf{a}\mathsf{b}^q\mathsf{a}\mathsf{b}^p\mathsf{a}^p\mathsf{b} \notin L$.
• If $x = \mathsf{a} \mathsf{b}^r$ for $0 \leq r < q$ (so that $y = \mathsf{b}^{q-r}$ with $q-r > 0$), then $xy^2z = \mathsf{a}\mathsf{b}^{p+q-r}\mathsf{a}^p\mathsf{b} \notin L$.

(Note that in the first case it is important that we can take $\ell = 0$ in the third property of the decomposition.)

_{The first two bullet points are really the same, and can both be done by "pumping" $y$ zero times. Since the case where $y$ consists entirely of $\mathsf{a}$s troubled the OP, I dealt with it separately.}

Answer 3

I have found the solution. It had a little catch.

Even if you choose the decomposition with $uv = a$ (for the word $ab^pa^pb$), the PL is giving you a contradiction, because $v = a$ and $uv^0w = a^0b^pa^pb = b^pa^pb$ and this word is not part of $L$ (because it has no $a$-s in the prefix).

Thanks you all for help!