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

51 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

$S \to aSb + 1 + a + b + aa + bb$ should work.