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

G1: The smallest strings possible to have an example case at hand.

S->aS->aB->ab

S->B->b

These are the smallest two strings that can be made.

It's evident from G1 is that no of a's can be 0 but no of b's is always more than 0.

So, it boils down to C or D.

Now, choosing C will mean, there can be 0 no of a's and 0 no of b's and the statement {a^m.b^n∣m≥0 or n>0} will still be true bcs it is connected by or, anyone being true is enough.

Clearly, this is unintended.

So, only option D is left and it's logically the ans too bcs we need (a>=0 and b>0) at the same time.

Answer 2

G1:
S→aS;
will generate any number of a’s and then we can have any number of b’s (greater than zero) after a’s by using he productions
S→B and B→b|bB
G2:
By using S→aA and then A→aA | ϵ we can have only any number of a’s (greater than zero) OR we can use A→B and B→bB | ϵ to add any number of b’s after a’s OR by using S→bB and B→bB | ϵ we can have only any number of b’s (greater than zero).

Answer 3

L(G1) = {a^+b^+ | b^+}
             {b, bb, bbb, ab, aab, abb, aabb, ...}
L(G2) = {a^+b* | b^+}
             {b, bb, bbb, …, a, aa, aaa, …, ab, aab, abb, ...}

A. {a^mb^n | m>0 or n>0} and {a^mb^n | m > 0 and n>0}
L1 generates strings of form a^+ when m = 1 and n = 0 which does not belong to L(G1). so this rules out option A.

B. {a^mb^n | m > 0 and n > 0} and {a^mb^n | m > 0 or n >= 0}
L1 here generates: {ab, aab, abb, aabb, ...} ; this Language does not contain strings like b, bb, and so on. so Option B is incorrect.

C. {a^mb^n | m >= 0 or n > 0} and {a^mb^n | m > 0 and n > 0}
L1 contains epsilon when m = 0 and n = 0; which clearly does not belong to L(G1).

D. {a^mb^n | m >= 0 and n > 0} and {a^mb^n | m > 0 or n > 0}
L1: {b, bb, bbb, …, ab, aab, abbb, ...} ; L2: {a, aa, aaa, …, b, bb, …, ab, aab, abb, aaabb, …}
L1 = L(G1) , L2 = L(G2)

hence, option D is correct.

Answer 4

why not C because both options C and D are the SAME!!!

Comments

They differ in AND and OR.

---

IF C is option machine can't accept single a or b hence D option