GATE CSE 2017 | Set 2 | Question: 16

Question

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$

• A. $\{a^mb^n \mid m \geq n, n > 0 \}$
• B. $ \{ a^mb^n \mid m \geq n, n \geq 0 \}$
• C. $\{a^mb^n \mid m >  n, n \geq 0 \}$
• D. $\{a^mb^n \mid m > n, n > 0 \}$

Comments

X will gives a^+

y will give a^nb^n where n ≥ 0

so language  is a^p a^nb^n  p >n and n ≥≥ 0 or  a^m b^n  m >n and n ≥ 0 or  where m = p+n

Answer is C

From below answers.

---

Looking at the grammar number of b’s generated will always be less than the number of a’s. and the second rule says the number of b’s = 0 => C is the answer

---

So it's like X and Y are two langages. X is Regular and Y is CFL.

And S is concatenation on these two.

---

the given grammar generates atleast one a and b can be zero , by looking at the options  a, d are eliminated as they states that n > 0,  for option b  it states that if n=0 then m>= n means m = n = 0 which is not true 
so ans is option C

---

followed same approach as defined by you!

Answer 1

$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.

Comments

@tvkkk ab and aabb cases are not possible.because X generated odd number of a and Y generated equal number of a and b.

---

is this language Reg?

I think yes.

Tell me the ans.

 

---

Option C

Answer 2

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

Answer 3

X will gives a⁺ 

y will give aⁿbⁿ where n $\geq$ 0 

so language  is a^p aⁿbⁿ  p >n and n $\geq$ 0 or  a^m bⁿ  m >n and n $\geq$ 0 or  where m = p+n

Answer is C

Answer 4

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

Answer 5

Option C

Comments

May I know the reason for downvote on this answer ??!

Answer 6

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