# Language Generated by a Grammar – Tutorial

# 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, a^{2}b, ab^{2}, a^{2}b^{2}, â¦â¦â¦}

= {a^{m} b^{n} | 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) = {a

^{m}b

^{n}| m â¥ 0 and n > 0}. We have to find out the grammar

**G**which produces

**L(G)**.

*Solution*

Since L(G) = {a^{m} b^{n} | 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) = {a

^{m}b

^{n}| m > 0 and n â¥ 0}. We have to find out the grammar G which produces L(G).

** Solution** –

Since L(G) = {a^{m} b^{n} | 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 })