0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ You wrote down wrong language. It is not $a^kb^k$. It is $a^kb^l$. And your grammar is wrong too. $\endgroup$
    – cs_student
    Sep 23 at 10:00
  • $\begingroup$ And why do write $a^*b^*$. Here we work with particluar word of the language $a^nb^nb^na^n$, not with language. $\endgroup$
    – cs_student
    Sep 23 at 10:06
  • $\begingroup$ @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. $\endgroup$
    – Nathaniel
    Sep 23 at 11:52
  • $\begingroup$ 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? $\endgroup$
    – cs_student
    Sep 23 at 16:46
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Sep 24 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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