Search code examples
context-free-grammarformal-languages

Construct a CFG for

L1 = { a^i b^j | i,j>=0 }

My attempt:

S = SA|e

A = aAB|e

B = bB|e

I have no way to confirm my answer, is this correct?

Solution

  • It's not correct because there's no way to get a single "b" (or any number of "b"s without any "a"s).

    (And I think you can fix it by changing just one letter ;o)

    PS Sorry for earlier incorrect reply; thought it was for i=j.