# Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \}$

I'm trying to find a CFG for the following language:

$$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \}$$

What I thought about unsuccessfully is the following:

$$S \rightarrow SASBS \mid SBSAS \mid \epsilon$$

$$A \rightarrow a \mid aa \mid aaa$$

$$B \rightarrow b \mid bb \mid bbb$$

Which has the following problems:

(1) It does not take into account words that do not have a's or b's

(2) It is possible to add a greater number of a's or b's than the allowed distance, for example aaabaaab is a word generated by that CFG

I've been thinking about it for a long time and it seems like a dead end because it seems that making CFG's is more of an art than anything else, I would greatly appreciate any help

• – D.W.
May 2 '21 at 21:28

You can write your language as a union of simpler languages: $$\{ a^{i+2} b^i : i \geq 0 \} \cup \{ a^{i+1} b^i : i \geq 0 \} \cup \{ a^i b^i : i \geq 0 \} \cup \{ a^i b^{i+1} : i \geq 0 \} \cup \{ a^i b^{i+2} : i \geq 0 \}$$