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$

  • 6
    $\begingroup$ You could simplify the task by splitting the language: $L = \{ a^i b^j \mid i < 2j \} \cup \{ a^i b^j \mid i > 2j \}$ $\endgroup$
    – Mike B.
    Feb 15, 2013 at 11:55
  • 4
    $\begingroup$ The reasoning being that CFG's are closed under union. $\endgroup$
    – Paresh
    Feb 15, 2013 at 11:59
  • 1
    $\begingroup$ Basically the question is already answered here: Context Free Grammar for language $\endgroup$ Feb 15, 2013 at 19:15

2 Answers 2


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.


Start with a grammar for $\{a^i b^{2 i} : i \ge 0\}$: $$ S \rightarrow a S bb \mid \epsilon $$ Now hack it so that there are more $a$ than $bb$: $$ \begin{align*} S &\rightarrow a S bb \mid A \\ A &\rightarrow a A \mid a \end{align*} $$ The modificaton to force more $b$ is similar, and left to you. It adds a nonterminal and three productions.

  • 3
    $\begingroup$ This will not generate strings of all $a$'s or all $b$'s, which are a part of $L$. $\endgroup$
    – Paresh
    Feb 15, 2013 at 13:49
  • $\begingroup$ If I change the question to i,j≥1 and i≠j and i<2j so how can i think of solution? $\endgroup$
    – user6885
    Feb 15, 2013 at 17:45
  • $\begingroup$ @Paresh, the part of extra $b$s is left to complete. And all $a$s is $S \Rightarrow A \Rightarrow^* a^k$. $\endgroup$
    – vonbrand
    Feb 15, 2013 at 18:06
  • $\begingroup$ Aah ... I don't know how I missed that. Sorry! $\endgroup$
    – Paresh
    Feb 15, 2013 at 18:11
  • $\begingroup$ @Vonbrand the problem that i dont know i to do the extra bso that it will not be more then the a. $\endgroup$
    – user6885
    Feb 15, 2013 at 20:13

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.