Context free language with valid Pumping Lemma use

Question

Is this language context free?

$L = \{a^kb^lb^ka^l \ | \ k,l \in \mathbb{N}\}$

Using Pumping Lemma and $z = a^nb^nb^na^n$ I find it contradicting PL.

If $z = uvwxy$ and $|vwx| \leq n$, follows:

1. $vwx$ is in either $a^n$ or $b^n$, second $b^n$, or second $a^n$. After pumping form of the word changes and thus pumped word not anymore in the language. Done

2. $vwx$ lies between $a^nb^n$ or $b^nb^n$ or $b^na^n$. When we pump down, we get $a^pb^qb^na^n$ or $a^nb^pb^qa^n$ or $a^nb^nb^pa^q$ with $p,q \leq n$. Which shows that pumped word not in the language.

Where is the error? The language should be context free. Why PL shows that language is not context free?

Answer 1

The language is indeed context-free. Since it can be defined as $L = \{a^kb^kb^la^l\mid k,l\geqslant 0\}$, the following grammar can generate it:

$S \rightarrow XY$

$X\rightarrow AXB\mid \varepsilon$

$Y\rightarrow BYA\mid \varepsilon$

In your tentative of proof, the second case is wrongly considered. You could have $vwx \in a^*b^*$ without any problem. For example, if $u=a^{n-1}$, $v =a$, $w=\varepsilon$, $x=b$ and $y = b^{2n-1}a^n$, then for any $k\geqslant 0$, $uv^kwx^ky = a^{n-1 +k}b^{2n-1+k}a^{n}\in L$.