I am trying to design a context-free grammar for the language $L = \{a^ib^jc^k \mid i\neq j+k\}$ over the alphabet $\Sigma = \{a,b,c\}$.

I know that I can split this up into the union of two cfg's $S_1$ and $S_2$,
where $S_1$ is the case where $\#_a \lt \#_b + \#_c$,
and $S_2$ is the case where $\#_a \gt \#_b + \#_c$.

I keep producing the grammar that generates this language but not in the correct order, that is I am having a hard time keeping the $a$'s on the left, $b$'s in the middle, and $c$'s to the right. Is this even context free?

  • 1
    $\begingroup$ What grammar have you produced so far? $\endgroup$ – Gilles Nov 18 '13 at 20:57

I would start by finding a CFG that generates the balanced version $\{a^ib^jc^k\mid i=j+k\}$ from nonterminal $C$.

$C\rightarrow aCc\mid B \\ B\rightarrow aBb\mid\varepsilon$

Now, as you correctly note, there are two possibilities on how to get the unbalanced version; either there is $(a^+)$ to the left, or $(b^+\mid b^*c^+)$ on the right. To deal with the former possibility, you simply add the following rules.

$ S\rightarrow aL\\ L\rightarrow aL\mid C $

You can deal with the other two possibilities in similar manner.

$ S\rightarrow R_bb\mid R_cc\\R_c\rightarrow R_cc\mid R_b\mid C\\R_b\rightarrow R_bb\mid B$


The split you made is actually a good design decision.

The language is context-free. Keep a central non-terminal, write $a$'s to the left, and $b,c$'s to the right. If you generate the $c$'s before you generate the $b$'s all letters stay in alphabetic order.


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.