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
$S \to aSb + 1 + a + b + aa + bb$ should work.