Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Your grammar has several other problems. For example, $T_1$ doesn't produce any string of non-terminals, and $a^i$ is produced by your grammar. Also, what is case 3 for? – Yuval Filmus Nov 1 '12 at 4:50
@YuvalFilmus just fixed it, can you propose a solution ? case 3 is for when b's equal c's, which is accepted. – Mike G Nov 1 '12 at 4:57
Hint: can you think of two grammars? One for $L_> = \{a^{i} b^{j} c^{k} \;|\; k > 2j\}$, and the other for $L_< = \{a^{i} b^{j} c^{k} \;|\; k < 2j\}$? Divide and conquer. Think of each problem at a time and don't try to combine them at the beginning – Ran G. Nov 1 '12 at 5:55
Another hint: $a^i$ is clearly not the difficulty here. Leave it out for the time being. – Raphael Nov 1 '12 at 14:16
up vote 4 down vote accepted

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.

share|cite|improve this answer

Here is my version of a grammar for $\{a^ib^jc^k \mid k\neq 2j \}$. It is based on the very straight-forward grammar for $\{a^ib^jc^k \mid k= 2j \}$, but then it requires to have either an additional (non-empty) sequence of bs or an additional (non-empty) sequence of cs to show up in the proper place. There is on special rule that produces $a^*bc$.

$S\rightarrow AbBE \mid AECc \mid Abc$

$A\rightarrow aA \mid \varepsilon$

$B\rightarrow bB \mid \varepsilon$

$C\rightarrow cC \mid \varepsilon$

$E\rightarrow bEcc\mid \varepsilon$

share|cite|improve this answer

Your Answer


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.