GATE CSE 2026 Session 1 Q52: Counts of a's and b's in strings of a given CFG

Theory of Computation
2 marks
MSQ
No negative marking

Consider the following context-free grammar $G$ .

$\begin{aligned} S &\to abaABAbba \\ A &\to aaBBAb \mid bBabaa \\ B &\to aBb \mid ab \end{aligned}$

In the above grammar, $S$ is the start symbol, $a$ and $b$ are terminal symbols, and $A$ and $B$ are non-terminal symbols.

Let $L(G)$ be the language generated by the grammar $G$ . For a string $s \in L(G)$ , let $n_1(s)$ be the number of $a$ 's in $s$ and $n_2(s)$ be the number of $b$ 's in $s$ .

Which of the following statements is/are true?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: B, D (official GATE 2026 final answer key)

Concept used: Track the difference (and ratio) of $a$ 's and $b$ 's each non-terminal contributes.

First step: $B$ always yields $a^k b^k$ ; $A \to bBabaa$ adds one more $a$ than $b$ , and $A \to aaBBAb$ adds one more $a$ than $b$ per step.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 1 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2026 Session 1 questions →

GATE CSE 2026 Session 1 Q52: Counts of a's and b's in strings of a given CFG

Question

Full step-by-step solution

More Theory of Computation PYQs