Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Related to this question on cs.SE. – Raphael May 17 '12 at 1:02
up vote 8 down vote accepted

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

share|cite|improve this answer
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

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

I hope I am correct.

share|cite|improve this answer
Your production can yield $S \rightarrow aSb \rightarrow aaScb \rightarrow aaabcb$ which is not in the language. – arjafi Sep 16 '12 at 14:00
Don't hope; verify. – MJD Sep 16 '12 at 16:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.