Consider the following context-free grammar 𝐺.
𝑆→𝑎𝑏𝑎𝐴𝐵𝐴𝑏𝑏𝑎
𝐴→𝑎𝑎𝐵𝐵𝐴𝑏 | 𝑏𝐵𝑎𝑏𝑎𝑎
𝐵→𝑎𝐵𝑏 | 𝑎𝑏
In the above grammar, 𝑆 is the start symbol, 𝑎 and 𝑏 are terminal symbols, and 𝐴 and
𝐵 are non-terminal symbols.
Let 𝐿(𝐺) be the language generated by the grammar 𝐺. For a string 𝑠∈𝐿(𝐺), let
𝑛1(𝑠) be the number of 𝑎’s in 𝑠 and 𝑛2(𝑠) be the number of 𝑏’s in 𝑠.
Which of the following statements is/are true?

Question

A grammar is given:
$E \rightarrow E + T \mid T$
$T \rightarrow T * F \mid F$
$F \rightarrow (E) \mid id$
For the input: $id + id * id$, what is the correct interpretation?

Answer 1

A cleaner way to see this is with weight functions on the terminals.

Define two weight assignments and extend them additively over any derived string: $w_1(a)=1, w_1(b)=-1$ (this measures $n_1-n_2$), and $w_2(a)=1, w_2(b)=-2$ (this measures $n_1-2n_2$). We track the sign of $w_1$ and $w_2$ through the grammar.

Nonterminal B: $B \to aBb \mid ab$. Each rule adds one $a$ and one $b$, so $w_1(B) = 0$ for every derivation (B is always balanced, with a-count $=$ b-count $= k \ge 1$). For $w_2$: $ab$ gives $1-2=-1$, and each wrap of $aBb$ adds another $1-2=-1$. So $w_2(B) = -k \le -1$ always.

Nonterminal A: $A \to aaBBAb \mid bBabaa$. For $w_1$: the terminals of $bBabaa$ alone give $1-2\cdot(-1)$... more directly, direct letters give $w_1=+1$ in the base rule and $w_1=+1$ in the direct letters of the recursive rule too (the two B's contribute $0$ each since B is balanced). So $w_1(A) = 1$ (base) or $w_1(A) = 1 + w_1(A')$ (recursive), which forces $w_1(A) \ge 1$ for every derivation -- A always has strictly more a's than b's.

For $w_2$: the base rule's direct letters $b,a,b,a,a$ contribute $3(1) + 2(-2) = -1$, plus the attached B contributes $w_2(B) \le -1$, so the base case gives $w_2(A) \le -2$. The recursive rule's direct letters $a,a,b$ contribute $2(1)+1(-2)=0$, plus two B's each contributing $\le -1$, plus the nested $A'$. So $w_2(A) \le -2 + w_2(A')$, meaning $w_2(A)$ only gets more negative with recursion. Hence $w_2(A) \le -2$ for every derivation, i.e. $n_1(A) < 2n_2(A)$ with a safety margin of at least 2.

Putting it together for S: $S \to abaABAbba$ has direct letters $a,b,a,b,b,a$, which are perfectly balanced: $w_1 = 0$ and $w_2(\text{direct}) = 3(1)+3(-2) = -3$. Adding the pieces (two A's and one B):

$w_1(s) = w_1(A_1) + w_1(A_2) + w_1(B) \ge 1 + 1 + 0 = 2 > 0$, so $n_1(s) > n_2(s)$ for every string -- this makes the claim 'For every string, $n_1 \ge n_2$' TRUE, and the claim 'some string has $n_1 < n_2$' FALSE.

$w_2(s) = -3 + w_2(A_1) + w_2(A_2) + w_2(B) \le -3-2-2-1 = -8 < 0$, so $n_1(s) < 2n_2(s)$ for every string -- this makes the claim 'For every string, $n_1 \le 2n_2$' TRUE, and the claim 'some string has $n_1 > 2n_2$' FALSE.

Conclusion: only the two 'for every string' statements survive -- the second and fourth options. Final answer: B and D.

Show Hint

The Correct Option is B, D

Solution and Explanation

Top Questions on Context Free Languages and Pushdown Automata

Questions Asked in GATE CS exam