## IDENTIFY LANGUAGE FROM GRAMMAR

Example 5Construct the language generated from the given grammar

G1 = ({S}, {a, b}, {S}, {P})

P:  S → aS | bS | λ

Solutions:

There are three productions S → aS, S → bS, S → λ are combined as a whole in a given production rule of the grammar G.

Now, which type of string we can generate for this grammar:

For S → λ [We can get only empty string λ]

1) S → aS → a . λ = a [S replace by λ]

2) S → aS → abS → ab [S → bS, S → λ]

3) S → aS → abS → abaS → aba [S → bS, S → aS, S → λ]

4) S → bS → b. λ= b [S replace by λ]

5) S → bS → b. aS → ba [S → aS S → λ]

6) S → bS → b. aS → ba. bS → bab [S → aS , S → bS, S → λ]

Actually, from this grammar, we can generate all strings generated by a,b including λ.

If = {a,b} then ∑*= {λ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, …} = (a + b)*

Here L(G1) = (a,b)*= {λ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, …} = (a + b)*

(set of all string generated by a,b including λ)

This grammar G1 = ({S}, {a, b}, {S}, {P}), P:  S → aS | bS | λ for  (a + b)*

If we slightly change the production, we can get the grammar of

= {a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, …} =

G2 = ({S}, {a, b}, {S}, {P})

S → aS | bS | a | b  from this production it is clear that we never get λ i.e. language does not contain any empty string λ.

So, the Language of the grammar is L(G2) = {a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, …}

Here L(G2) = ${\left(\mathrm{a},\mathrm{b}\right)}^{+}$= {a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, …} =

(set of all string generated by a,b excluding empty string  λ)

This grammar G2 = ({S}, {a, b}, {S}, {P}), P: S → aS | bS | a | b  for