# Context free language with valid Pumping Lemma use

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?

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$$.

• You wrote down wrong language. It is not $a^kb^k$. It is $a^kb^l$. And your grammar is wrong too. Sep 23, 2022 at 10:00
• And why do write $a^*b^*$. Here we work with particluar word of the language $a^nb^nb^na^n$, not with language. Sep 23, 2022 at 10:06
• @cs_student a word of the language $a^kb^lb^ka^l = a^kb^{l+k}a^l = a^kb^kb^la^l$. Also I wrote $a^*b^*$, to express "$vwx$ lies between $a^nb^n$" more formally. Sep 23, 2022 at 11:52
• Shouldn't PL work for every combination? It seems in your case it only works for particular configuration. When there are different number of a's and b's in v and x, when pumping we get result, that doesn't sum up as elegantly as in your example. Or am I doing something wrong? Sep 23, 2022 at 16:46
• Pumping lemma states that there exists a configuration that can be pumped. To prove that a language is not CFL, you have to prove that there isn't any configuration that can be pumped. That is why your proof failed: you didn't consider all configurations, and the one I proposed prove that $a^nb^nb^na^n$ cannot be a counter-example. Sep 24, 2022 at 8:37