[Solved]: Context Free Grammar for language

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 $2\times 2 > 3$ corresponding to production rule (1), how can I fix this?

Asked By : Mike G

Answered By : Shashwat

Production for $\{b^jc^k\; |\; j\neq 2k \}$ can be written as

$B\rightarrow bBcc\;|\;bB_1\;|\;cB_2$

$B_1\rightarrow bB_1\;|\;b\;|\;c\;|\;\epsilon$

$B_2\rightarrow cB_2\;|\;c\;|\;\epsilon$

You can see that it can't accept $bbcccc$. We can use $B\rightarrow bBcc$ twice but the final $B$ would have to be substituted with either b or c.

It accepts $bbccc$ as $B\rightarrow (bBcc) \rightarrow b(bB_1)cc \rightarrow bb(c)cc$

For even number of cs $B\rightarrow bBcc$ can be used. For odd number of cs, an extra $B_1\rightarrow c$ can be used.

So $\{a^ib^jc^k\; |\; j\neq 2k \}$ has the following grammar

$S\rightarrow AB$

$A\rightarrow aA \;|\; \epsilon$

$B\rightarrow bBcc\;|\;bB_1\;|\;cB_2$

$B_1\rightarrow bB_1\;|\;b\;|\;c\;|\;\epsilon$

$B_2\rightarrow 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