Problem Detail: I am trying to design a context-free grammar for the language $L = {a^ib^jc^k mid ineq j+k}$ over the alphabet $Sigma = {a,b,c}$. I know that I can split this up into the union of two cfg’s $S_1$ and $S_2$,
where $S_1$ is the case where $#_a lt #_b + #_c$,
and $S_2$ is the case where $#_a gt #_b + #_c$. I keep producing the grammar that generates this language but not in the correct order, that is I am having a hard time keeping the $a$’s on the left, $b$’s in the middle, and $c$’s to the right. Is this even context free?
where $S_1$ is the case where $#_a lt #_b + #_c$,
and $S_2$ is the case where $#_a gt #_b + #_c$. I keep producing the grammar that generates this language but not in the correct order, that is I am having a hard time keeping the $a$’s on the left, $b$’s in the middle, and $c$’s to the right. Is this even context free?
Asked By : Data
Answered By : avakar
I would start by finding a CFG that generates the balanced version ${a^ib^jc^kmid i=j+k}$ from nonterminal $C$.
$Crightarrow aCcmid B Brightarrow aBbmidvarepsilon$
Now, as you correctly note, there are two possibilities on how to get the unbalanced version; either there is $(a^+)$ to the left, or $(b^+mid b^*c^+)$ on the right. To deal with the former possibility, you simply add the following rules. $ Srightarrow aL Lrightarrow aLmid C $ You can deal with the other two possibilities in similar manner.
$ Srightarrow R_bbmid R_ccR_crightarrow R_ccmid R_bmid CR_brightarrow R_bbmid B$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18126
