Language Generated by a Grammar examples

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

LG={W|W ? ?*, S ?G W}

If LG1 = LG2, 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.,

LG = {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 ?

LG = {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 LG.

Solution

Since LG = {am bn | m ? 0 and n > 0}

the set of strings accepted can be rewritten as ?

LG = {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 ? aabAccepted
S ? aS ? aB ? abB ? abb Accepted
Thus, we can prove every single string in LG is accepted by the language generated by the production set.