Applied Test Series

Question

How to approach with such questions. Do we have to generate strings to validate the property of the grammars ?

Comments

is the answer a^m, m>=0?

Answer 1

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$}