FOR FREE YEAR SOLVED

IDENTIFY LANGUAGE FROM GRAMMAR

 

Example 1Construct the language generated from the given grammar

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

P: S → aSb | λ

 

Solutions:

This grammar consists of two production rules S → aSb and S → λ are combine to gather into a single production.

S (Non-terminal) here the starting symbol, so we can start derivation from starting production S.

 

For S → λ (We can get only λ)

 

 

Every time we use the production S → λ to get the string like ab, aabb, aaabbb, aaaabbbb..

So, which type of string we can get from this grammar L(G) = {λ, ab, aabb, aaabbb, aaaabbbb…..}

i.e. same number of a’s & b’s where every time a’s followed by b’s and including a0 b0 = λ also.

Note: For any string ω,  ω . λ = ω . λ = ω

 

Note: Here range of n ≥ 0 so, we can apply n = 0 to get a0 b0 = λ and this is come because of S → λ  productions and λ contains in your language.

 

Another grammar which give same language

 

G2 = S → aAb | λ

A → aAb | λ

 

So, two grammars G1 and G2 are equivalent