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 c
s $B\rightarrow bBcc$ can be used. For odd number of c
s, 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
0 comments:
Post a Comment
Let us know your responses and feedback