FOR FREE CONTENT

IDENTIFY LANGUAGE FROM GRAMMAR

Example 2: Construct the language generated from the given grammar

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

 P: S → aSb | ab

Solutions:

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.

Comparison:

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’.