Which options are correct about n1(s) and n2(s) for the given CFG in GATE CS 2026 Q15?

Options A and D are correct. For every string s in L(G), n1(s) - n2(s) = 5 (n1 always exceeds n2 by exactly 5), making A true. Since strings have sufficiently large n2 (at least 9 or more), n2 >= 5 always holds, making n1 <= 2*n2 true (option D).

How do you find the difference n1-n2 for strings in a CFG?

Assign a value of +1 for each 'a' and -1 for each 'b' in every production rule. Compute the net contribution of each non-terminal recursively. The total difference for the start symbol gives a fixed constant for all strings in the language.

CFG Language: Count of a's vs b's in Generated Strings

Q: How do you find the difference n1-n2 for strings in a CFG?

Assign a value of +1 for each 'a' and -1 for each 'b' in every production rule. Compute the net contribution of each non-terminal recursively. The total difference for the start symbol gives a fixed constant for all strings in the language.

Computer Sciences > GATE 2026 SET-1 > Context Free Grammar

Consider the following context free grammar:

S → abaABAbba
A → aaBBAb | bBabaa
B → aBb | ab

L(G) is the language generated by the grammar. For a string s ∈ L(G), let n₁(s) be the number of a's in s and n₂(s) be the number of b's in s. Which of the following is/are correct?

For every string s ∈ L(G), n₁(s) ≥ n₂(s)

There is a string s ∈ L(G), n₁(s) ≥ 2n₂(s)

For every string s ∈ L(G), n₁(s) < n₂(s)

For every string s ∈ L(G), n₁(s) ≤ 2n₂(s)

Correct : a,d

The correct answers are A and D.
The key insight is to compute the fixed difference d = n₁(s) - n₂(s) for all strings in L(G) by analyzing each production rule.
For B → ab: n₁ - n₂ = 1 - 1 = 0. So d_B = 0.
For A → aaBBAb: n₁ - n₂ = 2 + 2×0 - 1 + 1 = 2. So d_A = 2. (Both A-rules give 2 — consistent.)
For S → abaABAbba: n₁ - n₂ = (4-3) + d_A + d_B + d_A = 1 + 2 + 0 + 2 = 5.
So for every string s ∈ L(G): n₁(s) = n₂(s) + 5.
• A (n₁ ≥ n₂): Always true since n₁ = n₂ + 5 > n₂.
• B (n₁ ≥ 2n₂ for some s): Would need n₂ ≤ 5, but the minimum n₂ in any generated string is large (many b"s come from A and B productions), so this is false.
• C (n₁ < n₂): Always false since n₁ > n₂.
• D (n₁ ≤ 2n₂): n₂+5 ≤ 2n₂ ⇒ n₂ ≥ 5. Since all strings have n₂ well above 5, this always holds.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev