CREATE OWN LIBRARY

IDENTIFY LANGUAGE FROM GRAMMAR

Example 3: Construct the language generated from the given grammar

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

 P:   S → Ab            

       A → aAb | λ   

Solutions:

P:    S → Ab

       A → aAb | λ   ${\mathbf{a}}^{\mathbf{n}\mathbf{ }}{\mathbf{b}}^{\mathbf{n}}\mathbf{ }\mathbf{|}\mathbf{ }\mathbf{n}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{0}$      [For details see example 1]   

From production A → aAb | λ, we will get $a^{n }{b}^n | n \ge 0$

Then,

$\mathrm{A} \to {\mathrm{a}}^{\mathrm{n} }{\mathrm{b}}^{\mathrm{n}} | \mathrm{n} \ge 0$

$\mathrm{S} \to {\mathrm{a}}^{\mathrm{n} }{\mathrm{b}}^{\mathrm{n}} \mathrm{b} | \mathrm{n} \ge 0$ [We replace A by ${\mathrm{a}}^{\mathrm{n} }{\mathrm{b}}^{\mathrm{n}} | \mathrm{n} \ge 0$ at production S → Ab]

$\mathrm{S} \to {\mathrm{a}}^{\mathrm{n} }{\mathrm{b}}^{\mathrm{n}+1} | \mathrm{n} \ge 0$