edited by
349 views
1 votes
1 votes
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.
edited by

2 Answers

Best answer
3 votes
3 votes
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 by
1 votes
1 votes

We can try to elluminate the option . 

Find the smallest string in grammar and given options.

We get option d is right.

Related questions

1 votes
1 votes
1 answer
1
3 votes
3 votes
1 answer
2
all mix asked Jan 29, 2018
789 views
create a dfa with odd occurrence of sub string "abb" .and short cut for finding no.of states
2 votes
2 votes
1 answer
3
amrendra pal asked Aug 22, 2017
229 views
C = {ak | k is multiple of n }. Then how to show that for each n>=1, the language C is regular.
1 votes
1 votes
2 answers
4
Sona Barman asked May 22, 2018
3,012 views
Consider the vales of bst $11,22,33,44,55,66,77,88$.Which of the following is a valid sequence of preorder traversal?$55,33,11,22,44,77,66,88$$55,33,22,44,11,66,77,88$$55...