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

Thank you . Awesome approach.

---

very nice approach. Awesome.

---

@sushmita @Pragy Agarwal @Ram Sharma1 @Habibkhan @A_i_$_h @Bikram

How (b+)n= bnb∗

what property is this?

---

S ---> ε  and A ----> ε  also  so it also accepts ε    , so why not  option D  How can Option B generates ε

---

In Option B m<=n, when ε m=0 and m=0 . In option d it says any no. of a's followed by any no. of b's. Try generating aab from option d, it fails

---

The grammar never generates all strings with just b*.
For b* we have m=0 and n>=0. But these strings are not generated by the grammar.

Hence the condition needs to be

m<=n for all m>0
m=n for m=0

---

@rohith1001: Good observation. You're absolutely correct - the grammar cannot generate $b^+$, hence

$$L = \left \{ a^m n^n \mid \begin{align}
&m = n = 0 \\
&0 < m \leq n
\end{align} \right \}$$

---

@Pragy Agarwal how can i draw DFA for the given  grammar.? 

---

It is not Regular.

---

@Pragy Agarwal @kenzou

How can we write this?

---

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.

---

ayushsomani

\(S \rightarrow aSb\:|\: \epsilon\) is the grammar which produces language of type \( a^n b^n; \:\:n \geq0\)

So on the similar logic, \(S \rightarrow aSb^+\:|\: \epsilon\) is the grammar which produces language of type \( a^n (b^+)^n; \:\:n \geq0\)

Which further can be written as \( a^n b^n b^*; \:\:n \geq0\)

And leads to an answer as \( a^m b^n; \:\:m \leq n\)

---

I think the correct language will be: { $a^{m}b^{n} ; m<=n; m,n>=1$} $\bigcup$ {$\varepsilon $}

---

@SougataSarkar The given answer is correct. Actually $\epsilon$ is included in the Language 

$S = a^mb^n, \quad m\leq n$. And we don’t need to mention $m<=n; m,n>=1$ because only if it starts from 0, we will get $\epsilon$.

 

---

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