Problem Detail: The language is $L = {a^{i} b^{j} c^{k} ;|; k neq 2j}$. I’m trying to write a grammar for this language, what I have so far is: $S rightarrow AT_{1} ;|; AT_{2} ;|; AT_{3} ;|; AB ;|; AC$ $A rightarrow aA ;|; varepsilon$ $B rightarrow bB ;|; varepsilon$ $C rightarrow cC ;|; varepsilon$ $T_{1} rightarrow bbB’T_{1}c ;|; varepsilon $ (for $2j > k$)(1) $B’ rightarrow bB’ ;|; b$ $T_{2} rightarrow bT_{2}ccC’;|; varepsilon$ (for $2j < k$) $C’ rightarrow cC’ ;|; c$ $T_{3} rightarrow bT_{3}c ;|; varepsilon$ (for $j = k$) the problem that I am having is, the string $bbccc$ can’t be generated although valid, in that case $j = 2$ and $k = 3$ so $2times 2 > 3$ corresponding to production rule (1), how can I fix this?
Asked By : Mike G
Answered By : Shashwat
Production for ${b^jc^k; |; jneq 2k }$ can be written as $Brightarrow bBcc;|;bB_1;|;cB_2$ $B_1rightarrow bB_1;|;b;|;c;|;epsilon$ $B_2rightarrow cB_2;|;c;|;epsilon$ You can see that it can’t accept $bbcccc$. We can use $Brightarrow bBcc$ twice but the final $B$ would have to be substituted with either b or c. It accepts $bbccc$ as $Brightarrow (bBcc) rightarrow b(bB_1)cc rightarrow bb(c)cc$ For even number of cs $Brightarrow bBcc$ can be used. For odd number of cs, an extra $B_1rightarrow c$ can be used. So ${a^ib^jc^k; |; jneq 2k }$ has the following grammar $Srightarrow AB$ $Arightarrow aA ;|; epsilon$ $Brightarrow bBcc;|;bB_1;|;cB_2$ $B_1rightarrow bB_1;|;b;|;c;|;epsilon$ $B_2rightarrow cB_2;|;c;|;epsilon$ Note: i can be 0 but j and k can not be 0 simultaneously.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6415
