# Context Free Grammar for language L

Can someone help with this:

$L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$

I'm trying to write a grammar for this language? I tried this:

$S \to S_1 \mid S_2 \\ S_1 \to aXb \\ X \to aXb \mid aaXb \mid aab \\ S_2 \to aYb \\ Y \to aYb \mid Yb \mid b \\$

What do you think?

• Seems correct. Is there a problem? – Karolis Juodelė Feb 16 '13 at 11:46
• You should format your questions using MathJax in the future. You can learn more about the formatting by clicking on the "edit" link of a question to see its source. Most latex symbols work when used within '$' signs. You can look this up for a quick reference. – Paresh Feb 16 '13 at 13:37 ## 1 Answer The solution in the question is correct. The constraint$i\ne j$is the one that gives us trouble. To get around it we have to split into two cases: (i)$i<j$, and (ii)$i>j$(but still$i<2j$) thus$S\to S_{(i)} \mid S_{(ii)}$as the first production splits into this two cases. Now, divide and conquer: case (i) is very simple, since we only need$i<j$,$S_{(i)} \to aS_{(i)}b \mid B B \to Bb \mid b$This is your$S_2$. For case (ii), we need to$j< i < 2j$, so for every single$a$, the variable$C$will generate exactly one$b$, and at a certain point we switch to the variable$D$that will generate two$a$'s for each$b$.$S_{(ii)} \to aCb  C \to aCb \mid D D \to aaDb \mid aab$This is your$S_1$. • To get$i < j$you need$S_{(i)} \rightarrow a S_{(i)} b \mid B b$,$B \rightarrow B b \mid \epsilon$. The$B$alternative adds at least one$b\$ here. – vonbrand Mar 20 '13 at 13:29
• yes, you're right. – Ran G. Mar 20 '13 at 16:19