Problem Detail: Can someone help with this: $L={a^ib^j mid i,j ge 0 text{ and } i ne 2j}$ I’m trying to write a grammar for this language? I don’t know how to do this. I tried this:
$S rightarrow aaAb mid aA A rightarrow aA mid a$
$S rightarrow aaAb mid aA A rightarrow aA mid a$
Asked By : user6885
Answered By : Paresh
Consider the two languages:
$L_1 = {a^ib^j mid i, j ge 0 text{ and } i > 2j}$
$L_2 = {a^ib^j mid i, j ge 0 text{ and } i < 2j}$ Convince yourself that $L = L_1 cup L_2$. In $L_1$, the number of $a$’s are more than double of $b$’s, so there has to be atleast one $a$ (when there are no $b$’s). Also, for every addition of $b$, atleast 2 $a$’s must be added. You can generate $L_1$ as: $ S_1 rightarrow aA A rightarrow aaAb mid aA mid varepsilon $ $L_2$ is a little more tricky. The number of $a$’s are less than double the number of $b$’s, so there can be $0$ $a$’s, but non-zero $b$’s. Consider the “base case” of $1$ $b$. The string can be either $b$ or $ab$. We will let the first rule generate this base case. After that, notice that for every addition of $b$, we can increase the number of $a$’s by at most $2$. So we can add $0$, $1$, or $2$ $a$’s for every addition of $b$. We’ll let the second rule handle this. So, the CFG for $L_2$ becomes: $ S_2 rightarrow Bb mid aBb B rightarrow Bb mid aBb mid aaBb mid varepsilon $ Note that CFG’s are closed under union, that is, the union of two CFG’s is also a CFG. So, to get the CFG for $L$, let the starting state $S$ of $L$ lead to either the starting state of $L_1$, or of $L_2$: $S rightarrow S_1 mid S_2$ The rest of the rules remain the same as in the two languages. There may be a simpler grammar, but this was the first that came to mind.
$L_1 = {a^ib^j mid i, j ge 0 text{ and } i > 2j}$
$L_2 = {a^ib^j mid i, j ge 0 text{ and } i < 2j}$ Convince yourself that $L = L_1 cup L_2$. In $L_1$, the number of $a$’s are more than double of $b$’s, so there has to be atleast one $a$ (when there are no $b$’s). Also, for every addition of $b$, atleast 2 $a$’s must be added. You can generate $L_1$ as: $ S_1 rightarrow aA A rightarrow aaAb mid aA mid varepsilon $ $L_2$ is a little more tricky. The number of $a$’s are less than double the number of $b$’s, so there can be $0$ $a$’s, but non-zero $b$’s. Consider the “base case” of $1$ $b$. The string can be either $b$ or $ab$. We will let the first rule generate this base case. After that, notice that for every addition of $b$, we can increase the number of $a$’s by at most $2$. So we can add $0$, $1$, or $2$ $a$’s for every addition of $b$. We’ll let the second rule handle this. So, the CFG for $L_2$ becomes: $ S_2 rightarrow Bb mid aBb B rightarrow Bb mid aBb mid aaBb mid varepsilon $ Note that CFG’s are closed under union, that is, the union of two CFG’s is also a CFG. So, to get the CFG for $L$, let the starting state $S$ of $L$ lead to either the starting state of $L_1$, or of $L_2$: $S rightarrow S_1 mid S_2$ The rest of the rules remain the same as in the two languages. There may be a simpler grammar, but this was the first that came to mind.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9804
