Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
Related to this question on cs.SE. –  Raphael May 17 '12 at 1:02
add comment

2 Answers 2

up vote 7 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|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
1  
@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
add comment

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

I hope I am correct.

share|improve this answer
1  
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
    
Don't hope; verify. –  MJD Sep 16 '12 at 16:55
add comment

Your Answer

 
discard

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.