FOR FREE CONTENT

IDENTIFY LANGUAGE FROM GRAMMAR

Example 4: Construct the language generated from the given grammar

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

P:  S → aS | λ

Solutions:

There are two productions S → aS and S → λ combines to gather in the given grammar.

For S → λ (We can get only empty string λ)

[∴ ω . λ = ω . λ = ω.]  

Every time we use the production S → λ to get the string like a, aa, aaa, aaaa..

So, which type of string we can get from this grammar L(G1) = {λ, a, aa, aaa, aaaa…..}

i.e. Any string generated by only ‘a’ including $a^0$ = λ. 

Here L(G1) = {$a^n | n \ge 0$} = {λ, $a, a^2, a^3, a^4 ....$}  = a* (set of all string generated by ‘a’ including λ. )

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

If we slightly change the production, we can get the grammar of $a^{+}= \{a, a^2, a^3, a^4 ....\}$

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

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

Here,

This grammar G = ({S}, {a, b}, {S}, {P}), P:  S → aS | ab for ${\mathit{a}}^{\mathbf{+}}$