# Complement of $a^n b^n c^n$

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) 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!) – 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.

• 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 } – AVC Mar 16 '16 at 3:45

First note that strings in $$L= \{a^ib^jc^k: i=j=k\ge 0\}$$ have a specific order and specific count of the symbols. The complement of $$L$$ (denoted as $$L'$$) then includes every string over the alphabet $$\{a,b,c\}$$ that does not satisfy the order and/or the count constraints. This implies that $$L'$$ consists of the following languages over the alphabet $$A=\{a,b,c\}$$:

1. To relax the order constraint: a string in $$L'$$ could have either $$ba, ca$$, and/or $$bc$$ as a substring. This can be represented as the regular expression: $$(a+b+c)^*(ba+cb+ca)(a+b+c)^*$$.
2. To relax the count constraint: a string $$w$$ in $$L'$$ could have either $$i\ne j$$, $$i\ne k$$, or $$j\ne k$$. Clearly, part 1 is a regular language and part 2 is CF, and hence their union $$L'$$ is CF.
• Welcome to CS@SE. There's a typo in and/or bc as a. I didn't recognise ^ as part of a regular expression. – greybeard Dec 5 '19 at 7:27

Note that every string in $$\{a,b,c\}^*$$ starts with a string from $$L$$ (even if in some cases that string is the empty string, with $$n$$=0).

If a string is not in $$L$$ then the prefix $$a^nb^nc^n$$ (for largest possible $$n$$) is followed by a non-empty suffix.