# 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?

-

1
Seems correct. Is there a problem? – Karolis Juodelė Feb 16 at 11:46
– Paresh Feb 16 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 at 13:29
yes, you're right. – Ran G. Mar 20 at 16:19
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8735233545303345, "perplexity_flag": "middle"}