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.
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.
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\}$.
You can just reduce that to a single production as S -> aSc | aSb | ab
I hope I am correct.