+1 vote
104 views
Identify the language generated by the following grammar:

$S->AB$

$A->aAb|\epsilon$

$B->bB|b$

(A)$\{a^m b^n|n≥m, m>0\}$

(B)$\{a^m b^n|n≥m, m≥0\}$

(C)$\{a^m b^n|n>m, m>0\}$

(D)$\{a^m b^n|n>m, m≥0\}$

I select option C but it is wrong, correct answer is option D.

edited | 104 views
0
You marked answer C. Which is Quite close to D, Difference is Just that number of $a's$ could also be $0$.

Language Generated by Variable $A$ is $\left \{ a^mb^m | m\geq 0 \right \}$

Language generated by Variable $B$ is $\left \{ b^k | k> 0 \right \}$

So, Language generated by Variable $S$ will be Concatenation of above languages. Hence, $\left \{ a^mb^mb^k|m\geq 0,k> 0 \right \}$  Which can also be written as $\left \{ a^mb^n|m\geq 0,n>m \right \}$
selected
+1 vote

We can try to elluminate the option .

## Find the smallest string in grammar and given options.

We get option d is right.

+1 vote
1
+1 vote
2