356 views

1 Answer

Best answer
2 votes
2 votes

G1 :

$S → XA$

$X → aXb  |  \epsilon$

$A → Aa | \epsilon$

Here A generate a* and X generates {$a^{n} b^{n} | n >= 0$}

Therefore G1 generates ${L_{1}} = $ {$a^{n} b^{n}  a^{*} | n>= 0$}


G2 :

$S → AX$

$X → aXb  |  \epsilon$

$A → Aa | \epsilon$

Here A generate a* and X generates {$a^{n} b^{n} | n >= 0$}

Therefore G2 generates ${L_{2}} = $ {$a^{*} a^{n} b^{n} | n>= 0$}


Now,

${L_{1}} $ $\bigcap$ ${L_{2}} $ $=$ {$a^{n} b^{n}  | n>= 0$}

selected by

Related questions

3 votes
3 votes
2 answers
1
1 votes
1 votes
1 answer
2
0 votes
0 votes
1 answer
3
–1 votes
–1 votes
1 answer
4