Search code examples
context-free-grammarautomatacontext-free-language

Automata: CFG for following language


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) ?


Solution

  • 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}