1
$\begingroup$

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?

$\endgroup$
  • 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
2
$\begingroup$

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.

$\endgroup$
  • $\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
1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Welcome to CS@SE. There's a typo in and/or bc as a. I didn't recognise ^ as part of a regular expression. $\endgroup$ – greybeard Dec 5 '19 at 7:27
0
$\begingroup$

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.

$\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.