The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+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.

I could not understand Gradup answer explanation.Please help me to rectify my fault.
asked in Theory of Computation by Active (1.2k points)
edited by | 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$.

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 \}$
answered by Boss (24.9k 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.

answered by Boss (33.9k points)

Related questions

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
49,532 questions
54,126 answers
187,326 comments
71,046 users