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?