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 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.