So the complement of L1 = {$a^{n}b^{n}c^{n}$ | n $\geq$ 1} would be L2 = {a,b,c}* \ {$a^{n}b^{n}c^{n}$ | n $\geq$ 1}.

In other words, any combinations of a,b and c where we dont have an equal number of all three letters and w = $\varepsilon$ is also legit.

However, while I'm certain that there should be a contextfree grammar for L2, I can't seem to find a grammer that allows you to generate the terminals freely without allowing $a^{n}b^{n}c^{n}$ with n $\geq$ 1.

My attempt was to make a starting Rule S -> $Q_{_{a}}$ ; $Q_{_{b}}$ ; $Q_{_{c}}$ ; $\varepsilon$ so that the individual Q rules would make it possible for two of the terminals a, b and c to have an equal number, but not for the third. (in $Q_{_{a}}$, a is restricted by max(b,c), in $Q_{_{b}}$, b is restricted by max(a,c), in $Q_{_{c}}$, c is restricted by max(a,b) so that the restricted terminal can never show up as often as the unrestricted terminal with the highest count)

The rules I set up though, only allow to have unlimited numbers of unrestricted terminals in any order. I'm not sure how to implement a rule for the restricted terminal, without allowing it to have as high a count as the unrestricted ones, if the unrestricted ones have the same count.

here's my P for G$_{_{L2}}$ so far

S $\rightarrow$ $Q_{_{a}}$ ; $Q_{_{b}}$ ; $Q_{_{c}}$ ; $\varepsilon$

$Q_{_{a}}$ $\rightarrow$ $Q_{_{a}}$b $Q_{_{a}}$ ; $Q_{_{a}}$c $Q_{_{a}}$ ; $\varepsilon$

$Q_{_{b}}$ $\rightarrow$ $Q_{_{b}}$a $Q_{_{b}}$ ; $Q_{_{b}}$c $Q_{_{b}}$ ; $\varepsilon$

$Q_{_{c}}$ $\rightarrow$ $Q_{_{c}}$a $Q_{_{c}}$ ; $Q_{_{c}}$b $Q_{_{c}}$ ; $\varepsilon$

These are still missing the rules for the individual restricted variable. In what fashion can I add those, without breaking the [ $a^{n}b^{n}c^{n}$ | n = 0 ] rule?

Edit: it occured to me that I could refine the restricting rules, such that the restricted terminal can be derived from a rule if, and only if one (and only one) of the unrestricted ones is always created with it. For example:

S $\rightarrow$ $Q_{_{a}}$ ; $Q_{_{b}}$ ; $Q_{_{c}}$ ; $\varepsilon$

$Q_{_{a}}$ $\rightarrow$ $Q_{_{ab}}$b $Q_{_{ab}}$ ; $Q_{_{ac}}$c $Q_{_{ac}}$

$Q_{_{ab}}$ $\rightarrow$ $Q_{_{ab}}$b $Q_{_{ab}}$ ; $Q_{_{ab}}$c $Q_{_{ab}}$ ; $Q_{_{ab}}$ a $Q_{_{ab}}$ b $Q_{_{ab}}$ ; $Q_{_{ab}}$ b $Q_{_{ab}}$ a $Q_{_{ab}}$ ; $\varepsilon$

$Q_{_{ac}}$ $\rightarrow$ $Q_{_{ac}}$b $Q_{_{ac}}$ ; $Q_{_{ac}}$c $Q_{_{ac}}$ ; $Q_{_{ac}}$ a $Q_{_{ac}}$ c $Q_{_{ac}}$ ; $Q_{_{ac}}$ c $Q_{_{ac}}$ a $Q_{_{ac}}$ ; $\varepsilon$

At this point my brain starts running in circles. Would this set me on the right path?


You're overcomplicating. There is no need for the grammar to be deterministic, so it's OK for cases to overlap.

Say $\omega \in \overline{L_1}$. At least one of the following statements must be true:

  • $\omega = a^ib^j\nu \text{ where } i \ge 1, j\ge 0 \text{ and } i \ne j, \text{ and } \nu \text{ does not start with } b$
  • $\omega = a^ib^jc^k \text{ where } i, j, k \ge 1, \text{ and }j \ne k$
    (I don't require $i = j$, although if $i \ne j$ then the first condition also applies.)
  • $\omega \text{ does not start with } a$

These all have reasonably simple grammars.

Just in case it's not obvious, there are a few ways to do $a^jb^k | j\ne k$. One simple one:

$$\begin{align} S &\to A \mid B \\ A &\to aC \mid aA \\ B &\to Cb \mid Bb \\ C &\to \epsilon \mid aCb \end{align} $$

$C$ is a balanced sequence of $a$ and $b$, $A$ has more $a$s, $B$ has more $b$s, and $S$ has either more $a$s or more $b$s.


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.