context-free-grammarcontext-free-language

CFG for L={ a^n b^m : n <= m+3 , n,m>=0}

I want to find Context Free Grammar for L={ a^n b^m : n <= m+3 , n,m>=0}

What I have so far

S -> AAAB
A -> a | ε
B -> aBb | Bb | ε

Does this make any sense?

Solution

  • First of all this CFG should work properly But the CFG below is more readable :

    S -> aSb | A | B
A -> a | aa | aaa | ε
B -> bB | ε