I am trying to find the complement of the language $L = \{ a^n b^n c^n \mid n \ge 0\}$.

I know that one of the things I gotta do is take out $n \ge 0$ so $\{a^n b^n c^n \mid n > 0\}$ but I feel there is not enough.Is making it so $a^i b^j c^k$ so that $i \neq j \neq k$ enough and make it so that $i,j,k > 0$?

Or am I completely off track?

  • 1
    $\begingroup$ 1) What about $bca$? 2) If you write "$i \neq j \neq k$", do you mean that also $i \neq k$? (Chains of $\neq$'s don't make sense, it's not a transitive relation!) 3) What does it mean to "find" $\overline{L}$"? A description in which form? Mathematically, $\overline{L} = \{ w \in \{a,b,c\}^* \mid w \not\in L \}$ is a perfectly correct description. (Note that you have to fix the alphabet in for the complement operator to make sense!) $\endgroup$ – Raphael Mar 16 '16 at 10:20

The complement is the set of all strings over alphabet $\{a,b,c\}$ that are not of the form $a^i b^i c^i$ for some $i\geq 0$. That includes all strings $a^ib^jc^k$ where $i\neq j$, $i\neq k$ and/or $j\neq k$, as you say, but also some other strings. Mouse-over the box below for a hint.

For example, $bacbabc$ is in the complement.

  • $\begingroup$ Thank you for your response, I was thinking about that, then I would have to union { a c b} U { b c a} U {c a b } U { b a c} U { a c b } $\endgroup$ – AVC Mar 16 '16 at 3:45

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.