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
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 \}
$$