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.


migrated from stackoverflow.com Apr 30 '13 at 11:12

This question came from our site for professional and enthusiast programmers.


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