The Gateway to Computer Science Excellence
+1 vote
107 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.

I could not understand Gradup answer explanation.Please help me to rectify my fault.
in Theory of Computation by Active (1.2k points)
edited by | 107 views
0
You marked answer C. Which is Quite close to D, Difference is Just that number of $a's$ could also be $0$.

2 Answers

+2 votes
Best answer
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 \}$
by Boss (26.1k points)
selected by
+1 vote

We can try to elluminate the option . 

Find the smallest string in grammar and given options.

We get option d is right.

by Boss (35.4k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,242 answers
194,289 comments
95,941 users