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
    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?2012-05-16
  • 1
    @canton: No. All _production rules_ have to start from a single nonterminal.2012-05-16
  • 0
    @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.2012-05-16
  • 0
    Okay, well then this makes much more sense! Thank 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.

  • 1
    Your production can yield $S \rightarrow aSb \rightarrow aaScb \rightarrow aaabcb$ which is not in the language.2012-09-16
  • 0
    Don't hope; verify.2012-09-16