Consider the following context-free grammars$:$
$G_1: S → aS|B, B → b|bB$
$G_2: S → aA|bB, A → aA|B|ε, B → bB|ε$
Which one of the following pairs of languages is generated by $G_1$ and $G_2$, respectively?
- $\{a^mb^n|m > 0$ or $n > 0\}$ and $\{a^mb^n|m > 0$ and $n > 0\}$
- $\{a^mb^n|m > 0$ and $n > 0\}$ and $\{a^mb^n|m > 0$ or $n ≥ 0\}$
- $\{a^mb^n|m ≥ 0$ or $n > 0\}$ and $\{a^mb^n|m > 0$ and $n > 0\}$
- $\{a^mb^n|m ≥ 0$ and $n > 0\}$ and $\{a^mb^n|m > 0$ or $n > 0\}$
My attempt :
In $G_1$, there will be atleast $1$ b becase $S→B$ and $B→b$. But no of $A’s$ can be $0$ as well and no of $A$ and $B$ are independent. In $G_2$, either we can take $S→aA$ or $S→bB.$ So it must have atleast $1$ a or $1$ b. So, option $(4)$ is true.
Can you expainl in formal way, please?
Well, your grammars are in fact right regular and hence they generate regular languages. You could use the following algebraic approach to find the corresponding languages.
The language $S$ generated by $G_1$ satisfies the system of equations $S = aS+B$ and $B = b+bB$ (where $+$ denotes union). By Arden's rule, the second equation gives $B = bb^* = b^+$. Thus $S = aS + b^+$ and by Arden's rule again, $S = a^*b^+$.
Similarly, the language $T$ generated by $G_2$ satisfies the system of equations $T = aA + bB$, $A = aA+B+1$ and $B = bB + 1$ (here $1$ denotes the language reduced to the empty word). By Arden's rule, $B = b^*$, whence $A = aA + b^*$ and $A = a^*b^*$ and finally $T = aa^*b^* + bb^* = a^+b^* + b^+$. Thus (4) is the right choice.