I am trying to design a context-free grammar for the language $L = \{a^ib^jc^k \mid i\neq 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?
Asked By : Data
Answered By : avakar
I would start by finding a CFG that generates the balanced version $\{a^ib^jc^k\mid i=j+k\}$ from nonterminal $C$.
$C\rightarrow aCc\mid B \\ B\rightarrow aBb\mid\varepsilon$
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.
$ S\rightarrow aL\\ L\rightarrow aL\mid C $
You can deal with the other two possibilities in similar manner.
$ S\rightarrow R_bb\mid R_cc\\R_c\rightarrow R_cc\mid R_b\mid C\\R_b\rightarrow R_bb\mid B$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18126
0 comments:
Post a Comment
Let us know your responses and feedback