GATE IT 2006 | Question: 34

Question

In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string.

• $S \to aSAb \mid \epsilon$
• $A \to bA \mid \epsilon$

The grammar generates the language

• A. $((a + b)^* b)$
• B. $\{a^mb^n \mid m \leq n\}$
• C. $\{a^mb^n \mid m = n)$
• D. $a^* b^*$

Comments

How can we generate the string 'b' from this grammar?

---

@sristi30 there is no condition that m,n = 0.

---

same as part B

https://gateoverflow.in/678/gate2000-7

---

Start by eliminating options:

Option A –  This expression don't accept Eplison . But grammar given in question accept Eplison .

Option C –   This expression don't accept  strings like abb . But grammar given in question accepts abb .

Option D -This expression accept b as string but grammar given in question can’t accept b as string .

So option B is answer

Answer 1

$A \to bA \mid \varepsilon$

$\therefore \quad A = b^*$

---

$S \to aSAb \mid \varepsilon$

$\equiv S \to aSb^*b \mid \varepsilon$

$\equiv S \to aSb^+ \mid \varepsilon$

---

$S = a^n\left(b^+\right)^n, \quad n\geq 0$

$S = a^nb^nb^*, \quad n\geq 0$

$S = a^mb^n, \quad m\leq n$

Hence, option B is correct.

Comments

@Abhrajyoti00 Yes I agree with you that “ϵ” is already there in the language  {$a^{m}b^{n} ; m\leq n$} but this language also generates b* which is not generated by the grammar , that’s why I mentioned the condition m,n$\geq$1 along with “ϵ”

---

@SougataSarkar Yes you are correct. The smallest string which is not null is $ab$. Hence $m,n>=1 $ must be mentioned.

---

No option correct .

Answer 2

1) Epsilon is in grammar but can`t generate from this expression.
2) Can generate the exact language from this expression refer above answer.
3) abb is one of the string that can be generate from the given grammar but not by regular exp CONTRADICTION
4) aaaabb is the string that can be generated by this regular expression but not by grammar.

Comments

we can generate epsilon S-> epsilon

---

Same thing i mentioned , its the reason why $1^{st}$ one is not representing grammar because $1^{st}$ RE cannot generate $"\epsilon"$.

---

thank you

Answer 3

Option B is also wrong because option B says that we can generate any number of B, but they should be greater than equal to number of A. OPTION B can generate bbb, but  given CFG doesn't.

Answer 4

B is correct.

• A.  Incorrect as ((a+b)*b) can generate strings like aaaab which is not possible with given grammar.
• B.  Correct.
• C.  Also incorrect not always we will have a’s and b’s of same length, hence false
• D. a*b* can generate strings where a’s is greater than b false again.