Prove complement a^nb^nc^n is contextfree
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. 875
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? 875