FOR FREE YEAR SOLVED

IDENTIFY LANGUAGE FROM GRAMMAR

Example 6: Construct the language generated from the given grammar

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

P:  S → AB

     B → aBb | λ

     A → aA | λ   

Solutions:

From this production B → aBb | λ , we can get ${\mathit{a}}^{\mathbf{n}}\mathbf{ }{\mathit{b}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathit{n}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{0}$ and A → aA | λ will give you a*. 

 From B → aBb | λ  here we get  $\mathrm{B} \to {\mathrm{a}}^{\mathrm{n}} {\mathrm{b}}^{\mathrm{n}} | \mathrm{n} \ge 0$         

 From A → aA | λ  here we get   A → a*

If we apply both A and B at starting production S then,

$S \to AB \to a*a^{\mathrm{n}} b^{\mathrm{n}} | n \ge 0$  [Replace A by a* and B by  $a^{\mathrm{n}} b^{\mathrm{n}} | n \ge 0$]  

This range m ≥ n because if