CREATE OWN LIBRARY

Identify the language from the given grammar

Example 1: Construct 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

Follow the next examples:

1. Example 2: S→aSb|ab
2. Example 3: A→aSb|λ
3. Example 4: S→aS|λ
4. Example 5: S→aS|bS|λ