1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Nov 1 '12 at 4:50
  • $\begingroup$ @YuvalFilmus just fixed it, can you propose a solution ? case 3 is for when b's equal c's, which is accepted. $\endgroup$ – Mike G Nov 1 '12 at 4:57
  • 2
    $\begingroup$ 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 $\endgroup$ – Ran G. Nov 1 '12 at 5:55
  • 1
    $\begingroup$ Another hint: $a^i$ is clearly not the difficulty here. Leave it out for the time being. $\endgroup$ – Raphael Nov 1 '12 at 14:16
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.