retagged by
18,292 views
33 votes
33 votes

Identify the language generated by the following grammar, where $S$ is the start variable.

  • $ S \rightarrow XY$
  • $ X \rightarrow aX \mid a$
  • $ Y \rightarrow aYb \mid \epsilon$
  1. $\{a^mb^n \mid m \geq n, n > 0 \}$
  2. $ \{ a^mb^n \mid m \geq n, n \geq 0 \}$
  3. $\{a^mb^n \mid m >  n, n \geq 0 \}$
  4. $\{a^mb^n \mid m > n, n > 0 \}$
retagged by

11 Answers

Best answer
31 votes
31 votes

$S \to XY$

$X \to aX \mid a$

$Y \to aYb \mid \epsilon$


$X$ generates atleast one '$a$'. While $Y$ generates equal no of $a$'s and $b$'s( including epsilon).

$L = \{ a , aa, aaa, aab, aaaa, aaab,aaaaa, aaabb, \ldots\}$

Hence, answer should be Option C.

edited by
9 votes
9 votes
Strings can be a,aa,aab,aaab.

A and B are not correct because no of a's can never be equal to no of b's in the given grammar.

so it would either be C or D.

but in D it is given n > 0 which is wrong because of Y -> $\varepsilon$

 

Ans is C
edited by
7 votes
7 votes

X will gives a

y will give anbwhere n $\geq$ 0 

so language  is ap anb p >n and n $\geq$ 0 or  am b m >n and n $\geq$ 0 or  where m = p+n

Answer is C

3 votes
3 votes
Option C-As number of B's can be zero and number of A's are greater  than number of B's.
Answer:

Related questions

77 votes
77 votes
12 answers
3
Arjun asked Feb 14, 2017
28,050 views
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below:$$\...