Please have look at following language :
(a, b, c)* − {anbncn|n≥0}
My question is: How do I write a Context-Free Grammar for it ?
In general how can I write a grammar when something is excludes from it (i.e. has "-" sign) ?
There is no algorithm to determine whether a language is context-free. So it is not surprising that there is no general solution to the question you pose.
Context-free languages are not closed under complementation, set difference or intersection. (But they are closed under concatenation, set union, and Kleene star.) In any event
{anbncn|n≥0}
is not a context-free language, but its complement (as in your question) is context-free. The proof of this fact (by constructing a context-free grammar for the complement) is a standard example for the non-closure of CFGs under complementation.
In outline, your language L can be composed from the union of:
All strings over the alphabet {a,b,c}
where the letters are not in order. In other words, all strings which contain the substring ba
, cb
or ca
.
{aibjck|i,j,k≥0∧i≠j}
{aibjck|i,j,k≥0∧j≠k}