retagged by
18,302 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

1 votes
1 votes
We can solve this question by options so

By observing options we can say that:-

$\large NOTE$: It is just a pseudocode don't relate it with programming

$\text{/*Number of a's strictly greater than b's*/} $
$if (m>n)\{$

            $\text{/*0 b's possible -(C)*/ }$
            $if(n==0) C$

            $\text{/*0 b's not possible -(D)*/}$
            $else\space D$

$\}$

$\text{/*Number of a's greater than b's*/} $
$if(m>=n)\{$

         $\text{/*0 b's possible B*/}$
         $if(n==0)  B$

        $\text{/*0 b's not possible A*/}$
        $else\space A$      

$\}$

$S\longrightarrow XY\longrightarrow X\longrightarrow a$

so we can't prove $\#a = \#b$ it means $(m=n)$

so option A and B eliminated and n is also 0 it means 0 b's also possible so option D eliminated

Hence $\large Option C$ is right answer
edited by
Answer:

Related questions

77 votes
77 votes
12 answers
3
Arjun asked Feb 14, 2017
28,080 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:$$\...