0
$\begingroup$

i have seen this question where someone was asking if $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ is context free.

Then there was an answer that says that it is context free because:

The language, in turn, is context-free. This is because we can write it as a union of context-free languages:

  • Words not of the form $a^*c^*b^*$

  • Words of the form $a^nb^mc^k$ where 𝑛>𝑚

  • Words of the form $a^nb^mc^k$ where 𝑚>𝑘.

So my question is, why can't i take the language $\{a^nb^nc^k | n > m > k\}$?

Isn't that also the complement of the language?

If so, that would be pumpable with the word z = $a^{n+2}b^{n+1}c^n$ right?

I am a little bit confused and feel like i missed something.

$\endgroup$

2 Answers 2

1
$\begingroup$

No. $\{a^nb^mc^k\mid n>m>k\}$ is not the complement of $\{a^nb^mc^k\mid n\le m\le k\}$, for two reasons.

(1) The negation of the logical statement "$P\land Q$" is not "$\lnot P\land \lnot Q$", it is "$\lnot P\lor \lnot Q$".

(2) The original language consists of only strings in the language $a^*b^*c^*$, so the complement must include all strings where the order of symbols is not alphabetical.

As a consequence the complement of "$n\le m\le k$" is then the union of three languages "$n>m$", "$m>k$", "not alphabetical", each of which is context-free. Occasionally the "not alphabetical" part $\{a,b,c\}^*\setminus a^*b^*c^*$ is overlooked, but as that is a regular language it is the least problematic part.

$\endgroup$
1
$\begingroup$

You ask:

Isn't that also the complement of the language?

Here that refers to $L' = \{a^n b^m c^k \mid n > m > k\}$ but I'm not sure what the language refers to. It could be $L=\{a^n b^m c^k \mid n \le m \le k\}$ or $L'' = \{a,b,c\}^* \setminus L$. In any case:

  • $L'$ is not the complement of $L$. As (one of the many possible choices for a) witness, notice that $b$ belongs to neither $L$ nor $L'$.

  • $L'$ is not the complement of $L''$. A witness is $aab$ since it belongs to both $L'$ and $L''$.

$\endgroup$

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.