# Context Free Grammar

How can a context free grammar be generated for the following language:

$$\{a^ib^jc^k : i = j + k\}$$

I assume that any production rule that places a $b$ or $c$ must also place an $a$ but I don't know how to do this while maintaining order.

-
Related to this question on cs.SE. –  Raphael May 17 '12 at 1:02

Start generating $c$s and $a$s, by say the rule $S \to aSc$ ($S$ the start variable), we need a possibility to switch to $b$s, by say $S \to T$. The rule $T \to aTb$ will generate $a$s and $b$s, and $T\to \epsilon$ (the empty word) will allow us to stop. So our grammar is $\{S \to aSc|T, T \to aTb|\epsilon\}$.

-
I thought that to say that it was context free all strings must be generated from only one variable, i.e. S the start variable. Is that incorrect? –  canton May 16 '12 at 8:48
@canton: No. All production rules have to start from a single nonterminal. –  Tara B May 16 '12 at 8:48
@martini: I was just about to write a hint and then your answer came up! I do think it would have been nicer to leave something for canton to figure out. –  Tara B May 16 '12 at 8:50
Okay, well then this makes much more sense! Thank you @TaraB and @martini! That was my point of confusion then! –  canton May 16 '12 at 8:50
Your production can yield $S \rightarrow aSb \rightarrow aaScb \rightarrow aaabcb$ which is not in the language. –  Arthur Fischer Sep 16 '12 at 14:00