edited by
11,942 views
51 votes
51 votes

Which of the following languages is generated by the given grammar?

$$S \rightarrow aS \mid bS \mid \varepsilon$$

  1. $\{ a^nb^m \mid n,m \geq 0\}$
  2. $\{ w \in \{ a,b\}^* \mid w\text{ has equal number of a's and b's}\}$
  3. $\{a^n \mid n \geq 0 \} \cup \{b^n \mid n \geq 0\} \cup \{a^n b^n \mid n \geq 0\}$
  4. $\{ a,b\}^*$
edited by

5 Answers

Best answer
71 votes
71 votes

Correct Option: D

$S \rightarrow aS \mid bS \mid \varepsilon$

is $(a+b)^*$

edited by
13 votes
13 votes
It generates aba so A,B,C are wrong.
So,ANSWER D
5 votes
5 votes

For option A  order is fixed  Any number of a  and after that any number of b . so it cannot generate abbaa  so wrong .

For option B equal number of a and equal number  of b  , bit order is not fixed  but it can also not generate  abbaa so wrong .

For Option C  order is fixed  either a   or b or any number of a followed by any number of b , It also cannot generate abbaa  so wrong.

For option D no order   is fixed we can generate any string . so solution is D

ANSWER D

1 votes
1 votes
S --.> aS | bS | €

we can get o/p as    S---> ab

                                        ba

                                       aaaaaaaaaaaaaaa...

                                     bbbbbbbbbbbbbbbb....

                                     abababbabababbab.....

 

now in options

a -ab ( a is followed by b its nessary )

b - equal no. of and b (which is not nessar)

c-same as option b

d) you can generate any no. of a and any no. of b and also €

so d is correct one
Answer:

Related questions