Identify the language from the given grammar


Example 1Construct the language generated from the given grammar

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

P: S → aSb | λ



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|λ