Find the grammar of the language 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) = {a, aa, ab, aaa, aab ,abb, …….}
Here, the start symbol has to take at least one ‘a’ followed by any number of ‘b’ including null.

To accept the string set {a, aa, ab, aaa, aab, abb, …….}, we have the  following productions:
S → aA, A → aA , A → B, B → bB ,B → λ
S → aA → aB→ aλ→a (Accepted)
S → aA → aaA→ aaB → aaλ→aa (Accepted)
S →aA →aB→abB→ abλ → ab (Accepted)
S → aA → aaA→ aaaA→aaaB → aaaλ→aaa (Accepted)
S → aA → aaA→ aaB→aabB → aabλ→aab (Accepted)
S → aA → aB→ abB→abbB → 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 is:
G: ({S, A, B}, {a, b}, S, {S → aA, A → aA | B, B → λ | bB })

Leave a Reply