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

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

---

No option correct .

---

Yes m,n>=1 must be mentioned in the question if in this economy this question is asked they  will definitely mention every detail but at that time many  questions lack detailing

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.

Answer 5

Option A:
((a + b)* b)* → It accepts string aa but given grammar does not accepts.
Option C&D:
→ abb accepted by given grammar but option C & D are not accepting.

Answer 6

The correct answer is B. $\{a^m b^n \mid m \le n\}$.

---

 

 Here is the step-by-step reasoning:

 

Let's analyze the number of a's and b's generated by the rules.

1. Analyze Non-Terminal A:

   • The rules for A are $A \to bA \mid \epsilon$.

   • This is a standard grammar that generates zero or more b's.

   • So, the language for A is $L(A) = b^*$.

2. Analyze Non-Terminal S:

   • The rules for S are $S \to aSAb \mid \epsilon$.

   • The base case is $S \to \epsilon$. This generates the empty string, where $m=0$ and $n=0$. This satisfies the condition $m \le n$.

   • The recursive case is $S \to aSAb$. Let's see what this rule adds to the string:

     • It adds exactly one a.

     • It adds exactly one b.

     • It adds one non-terminal A, which (as we found in step 1) generates $b^*$ (zero or more b's).

3. Putting It Together:

   • To generate any string, we must apply the recursive rule $S \to aSAb$ some number of times, let's say $m$ times.

   • This will produce exactly $m$ a's.

   • It will also produce $m$ b's (one from each application of the rule) plus $m$ $A$'s.

   • Each of these $m$ $A$'s will contribute some number of b's (let's say $k_1, k_2, \dots, k_m$ b's, where each $k_i \ge 0$).

   • The total number of b's, $n$, will be: $n = m + k_1 + k_2 + \dots + k_m$.

   • Since all $k_i \ge 0$, the sum $(k_1 + \dots + k_m)$ must be $\ge 0$.

   • Therefore, the total number of b's is $n = m + (\text{a number } \ge 0)$.

   • This means $n \ge m$, which is the same as $m \le n$.

Example Derivation (for $abbb$):

1. $S \Rightarrow aSAb$ (Here $m=1$. We have one a, one b, and one $A$. We need $n \ge 1$)

2. $S \Rightarrow a(\epsilon)Ab$ (Used $S \to \epsilon$)

3. $S \Rightarrow aAb$

4. $S \Rightarrow a(bA)b$ (Used $A \to bA$)

5. $S \Rightarrow a(bbA)b$ (Used $A \to bA$ again)

6. $S \Rightarrow a(bb\epsilon)b$ (Used $A \to \epsilon$)

7. $S \Rightarrow abbb$

The resulting string is abbb. Here, $m=1$ (one a) and $n=3$ (three b's). The condition $m \le n$ (or $1 \le 3$) is true.