Identify the language from the given grammar


Example 2: Construct the language generated from the given grammar

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

 P: S → aSb | ab



This grammar consists of two production rules S → aSb and S → ab 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 → ab (We can get only ‘ab’)



Every time we use the production S → ab 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 and b’s where every time a’s followed by b’s with at least one ab.


Note: Here range of n ≥ 1 so, λ is not allowed in your language because this language contains at least ‘ab’ string.




Same number a’s and b’s where a followed by b and this language contains λ also that’s the reason n ≥ 0.


Same number a’s and b’s where a followed by b but this language does not contain λ also that’s the reason n ≥ 1. This language contains at least one length of string ‘ab’. 


Follow the next examples:

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