2
$\begingroup$

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.

  • 2
    Related to [this question on cs.SE](http://cs.stackexchange.com/questions/1556/is-a-w-in-a-b-c-mid-aw-2-bw-3-cw-a-cfg).2012-05-17

2 Answers 2

8

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\}$.

  • 0
    Okay, well then this makes mu$c$h more sense! Th$a$nk you @TaraB and @martini! That was my point of confusion then!2012-05-16
-4

You can just reduce that to a single production as S -> aSc | aSb | ab

I hope I am correct.

  • 0
    Don't hope; verify.2012-09-16