Find the grammar for the L (G) = {a^m b^n | m ≥ 0 and n > 0}

Since L(G) = {am bn | m ≥ 0 and n > 0} the set of strings accepted by the language can be written as:

L(G) = {b, ab,bb, aab, abb, …….}

Here, the start symbol has to take at least one ‘b’ preceded by any number of ‘a’ including null.

To accept the string set {b, ab, bb, aab, abb, …….}, we have taken the productions:
S →aS , S →B, B → b and B → bB
S →B→ b (Accepted)
S →B→ bB → bb (Accepted)
S →aS →aB→ab (Accepted)
S →aS →aaS →aaB → aab(Accepted)
S →aS →aB→abB→ abb (Accepted)

Thus, we can prove every single string in L(G) is accepted by the language generated by the production set.
Hence the grammar:

G: ({S, A, B}, {a, b}, S, { S →aS | B , B → b | bB })

Leave a Reply