I'm stuck on this question about context-free languages and was hoping for some clarification.

$\qquad L = \{a^i b^j c^k \mid i=j, i=k\}$

is not context-free. Show that its complement is context-free.

I understand that the complement basically means everything not in $L$, that is $A^* \setminus L$. However, I have no idea how to actually take a complement for a language like this.


You are right. The complement consists of all strings not in the language. So basically if the language says "all strings such that X holds" the complement is "all strings such that not X holds", the logical negation of X.

In this case the logical negation of "$i=j$ and $i=k$" equals "not ($i=j$ and $i=k$)" or using the Morgan's rule, "$i\neq j$ or $i\neq k$".

But there is a slight catch. Actually the strings in $L$ have an additional explicit condition, they are of the form $a^i b^j c^k$ for some $i,j,k$. That means the actual complement is the union of (1) all strings not of the form $a^i b^j c^k$ (thus, not in $a^* b^* c^* $) and (2) all strings of the form $a^i b^j c^k$ such that "$i\neq j$ or $i\neq k$".

The strings in (1) form the regular language $\{a,b,c\}^* - a^* b^* c^* $ and should not bother you too much. The strings in (2) are treated elsewhere in this forum.


In order for a string not to be in language $L$, either $i \neq j$ or $i \neq k$

Anytime we take the complement of a language which depends on variables equality, we make any (either or both) pair originally equal to unequal each other

so if $L =$ { $a^xb^y \mid x = y$} then $ L'=$ {$a^xb^y \mid x \neq y$}

  • $\begingroup$ This is wrong. In your example, $\overline{L} \supseteq (\{a,b\}^* \setminus \mathcal{L}(a^*b^*))$! $\endgroup$ – Raphael Apr 30 '13 at 21:58

Your Answer

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