# Language Generated by a Grammar

The set of all strings that can be derived from a grammar is said to be the language generated from that grammar. A language generated by a grammar G is a subset formally defined by

L(G)={W|W â â*, S âG W}

If L(G1) = L(G2), the Grammar G1 is equivalent to the Grammar G2.

### Example

If there is a grammar

G: N = {S, A, B} T = {a, b} P = {S â AB, A â a, B â b}

Here S produces AB, and we can replace A by a, and B by b. Here, the only accepted string is ab, i.e.,

L(G) = {ab}

### Example

Suppose we have the following grammar –

G: N = {S, A, B} T = {a, b} P = {S â AB, A â aA|a, B â bB|b}

The language generated by this grammar –

L(G) = {ab, a2b, ab2, a2b2, â¦â¦â¦}

= {am bn | m â¥ 1 and n â¥ 1}

## Construction of a Grammar Generating a Language

We`ll consider some languages and convert it into a grammar G which produces those languages.

### Example

Problem – Suppose, L (G) = {am bn | m â¥ 0 and n > 0}. We have to find out the grammar G which produces L(G).

Solution

Since L(G) = {am bn | m â¥ 0 and n > 0}

the set of strings accepted can be rewritten 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 })

### Example

Problem – Suppose, L (G) = {am bn | m > 0 and n â¥ 0}. We have to find out the grammar G which produces L(G).

Solution

Since L(G) = {am bn | m > 0 and n â¥ 0}, the set of strings accepted can be rewritten 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 taken the 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: ({S, A, B}, {a, b}, S, {S â aA, A â aA | B, B â Î» | bB })