GATE CSE 2016 Set 1 | Question: 42

Question

Consider the following context-free grammars;

$G_1 : S \to aS \mid B, B \to b \mid bB$

$G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$

Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ,respectively?

• A.  $\{ a^mb^n \mid m > 0 \text{ or } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ and } n >0\}$ 
• B.  $\{ a^mb^n \mid m > 0 \text{ and } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ or } n\geq0\}$
• C.  $\{ a^mb^n \mid m \geq 0 \text{ or } n >0\}$ and $\{ a^mb^n \mid m > 0\text{ and } n>0\}$
• D.  $\{ a^mb^n \mid m \geq 0 \text{ and } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$

Comments

C and D options are exactly similar 🤔

---

how option C is wrong expain with contradictory example ?

---

$ \{ a^mb^n \mid m \geq 0 \text{ and } n >0\}$ and$ \{ a^mb^n \mid m > 0 \text{ or } n>0\}$

can we can write option D as below ?

$ \{ a^mb^n \mid m \geq 0 \text{ and } n >0\}$ and$ \{ a^mb^n \mid m \geq 0 \text{  and } n \geq0\} $

Answer 1

Answer is (D).

$G_1$ results in strings $b, ab, bb, aab, abb, bbb,$ ... i.e $a^mb^n$, $m\geq 0$ and $n > 0$ (and because only $a$'s are not possible but only $b$'s are)

$G_2$ result in strings $a, b, aa, ab, bb, aaa, aab, abb, bbb$   ... i.e $a^mb^n$, $m > 0$ or $n > 0$ (or because only $b$'s is possible $b,bb,bbb,$ , only $a$'s are possible)

Comments

D is the correct answer. For G1, ‘b’ occurs atleast once.

---

in G2 language why they are not used greater than or equal to bcoz here m or n can also be equal to zero ?

---

Anyone please explain what is wrong when we choose option C as answer

i am confused that the how AND  and OR  creates difference here?

Answer 2

if we have given  right linear grammar,,,then it  is better to draw FA and then analyze the language

and we know null production corrresponds to final state and unit production corresponds to null moves  

now it is clear that

L1 = a* b*b = a*b⁺   =  {a^mbⁿ , m>=0 and  n>0}

and 

L2 = aa* + bb* +  a⁺ b⁺ = a⁺ + b⁺ +  a⁺ b⁺     =  {a^mbⁿ , m>0 or  n>0}

Comments

@Kushagra गुप्ता

You can't write RE for the given Grammar coz it's not either RLG or LLG or Type-3 Grammar.

---

@ayushsomani

It is extended right linear grammar. So we can write RE for it.

---

@Kushagra गुप्ता

How?

Answer 3

my ans is D.

beacuse in G1, a may be 0 or more... but we have to generate b.. "and" will be used in side g1.. not "or"

only option D consist it..no need to check G2 then.

plz correct me if wrong

Answer 4

(D) is correct..No need to check for G2, bcoz clarfying G1 there is no matching in 1st phase in any other option.