Question:hard
Consider the following grammar where \(S\) is the start symbol, and \(a\) and \(b\) are terminal symbols.
\[ S \rightarrow aSbS \mid bS \mid \epsilon \]
Which of the following statements is/are true?
Consider the following grammar where \(S\) is the start symbol, and \(a\) and \(b\) are terminal symbols.
\[ S \rightarrow aSbS \mid bS \mid \epsilon \]
Which of the following statements is/are true?
\[ S \rightarrow aSbS \mid bS \mid \epsilon \]
Which of the following statements is/are true?
Show Hint
Every application of \(aSbS\) fixes one \(a\) together with one \(b\); track how many ways the leftover \(b\)'s can be split between the two sub-copies of \(S\) to see when more than one parse tree exists.
Updated On: Jul 22, 2026
- The grammar is ambiguous
- The string \(abb\) has two distinct derivations in this grammar
- The string \(abab\) has only one rightmost derivation
- The language generated by the grammar is undecidable
Show Solution
The Correct Option is A, B, C
Solution and Explanation
Step 1: Reformulate the grammar as a counting rule.
Read $S \rightarrow aSbS \mid bS \mid \epsilon$ as: every generated string is built by repeatedly either (i) opening a new $a \dots b$ pair that itself contains two independent $S$-generated substrings glued around it, or (ii) prefixing a lone $b$, or (iii) stopping. Because rule (i) is the only source of $a$'s and always pairs each $a$ with its own $b$, and rule (ii) only ever adds extra $b$'s, every derivable string has (number of $b$'s) $\geq$ (number of $a$'s), with strict inequality whenever a rule (ii) step is used somewhere.
Step 2: Draw both parse trees for $abb$ in words.
Tree 1: root $S$ expands by rule (i) into $a$, left child $S_1 = \epsilon$, literal $b$, right child $S_2$; $S_2$ expands by rule (ii)+(iii) to the single letter $b$. Reading the leaves left to right gives $a,\epsilon,b,b \to abb$.
Tree 2: root $S$ expands by rule (i) into $a$, left child $S_1$, literal $b$, right child $S_2 = \epsilon$; $S_1$ expands by rule (ii)+(iii) to the single letter $b$. Reading the leaves left to right gives $a,b,b,\epsilon \to abb$.
Both trees yield the same string $abb$ but attach the extra $b$ to a different sub-copy of $S$, so they are genuinely different parse trees. This directly proves the grammar is ambiguous (option A true) and that $abb$ has (at least) two derivations (option B true).
Step 3: Show $abab$ cannot be split the same way.
List every way to divide the 3 letters that follow the initial $a$ (namely $bab$) between $S_1$, the fixed literal $b$, and $S_2$: putting 0 letters before the literal $b$ forces $S_2$ to spell $ab$, which only rule (i) with both inner copies empty can do -- a single fixed derivation; putting 1 letter before the literal $b$ would need that letter to equal the target's second character $a$, but the literal $b$ occupies that position by construction, a contradiction; putting 2 letters before the literal $b$ would need $S_1$ to spell $ba$, but a lone $a$ can never terminate a derivation of $S$ (Step 1), so this is impossible. Only one split survives, so $abab$ has a unique parse tree and therefore a unique rightmost derivation, confirming option (C).
Step 4: Decidability check for option (D).
Any language produced by a context-free grammar sits inside the class of context-free languages, and every context-free language has a decision procedure for membership (CYK runs in polynomial time on the length of the input string). So it is never correct to call a CFG's language undecidable, and option (D) fails.
Step 5: Final answer.
$\[ \boxed{\text{(A), (B), (C) are true; (D) is false}} \]$
Read $S \rightarrow aSbS \mid bS \mid \epsilon$ as: every generated string is built by repeatedly either (i) opening a new $a \dots b$ pair that itself contains two independent $S$-generated substrings glued around it, or (ii) prefixing a lone $b$, or (iii) stopping. Because rule (i) is the only source of $a$'s and always pairs each $a$ with its own $b$, and rule (ii) only ever adds extra $b$'s, every derivable string has (number of $b$'s) $\geq$ (number of $a$'s), with strict inequality whenever a rule (ii) step is used somewhere.
Step 2: Draw both parse trees for $abb$ in words.
Tree 1: root $S$ expands by rule (i) into $a$, left child $S_1 = \epsilon$, literal $b$, right child $S_2$; $S_2$ expands by rule (ii)+(iii) to the single letter $b$. Reading the leaves left to right gives $a,\epsilon,b,b \to abb$.
Tree 2: root $S$ expands by rule (i) into $a$, left child $S_1$, literal $b$, right child $S_2 = \epsilon$; $S_1$ expands by rule (ii)+(iii) to the single letter $b$. Reading the leaves left to right gives $a,b,b,\epsilon \to abb$.
Both trees yield the same string $abb$ but attach the extra $b$ to a different sub-copy of $S$, so they are genuinely different parse trees. This directly proves the grammar is ambiguous (option A true) and that $abb$ has (at least) two derivations (option B true).
Step 3: Show $abab$ cannot be split the same way.
List every way to divide the 3 letters that follow the initial $a$ (namely $bab$) between $S_1$, the fixed literal $b$, and $S_2$: putting 0 letters before the literal $b$ forces $S_2$ to spell $ab$, which only rule (i) with both inner copies empty can do -- a single fixed derivation; putting 1 letter before the literal $b$ would need that letter to equal the target's second character $a$, but the literal $b$ occupies that position by construction, a contradiction; putting 2 letters before the literal $b$ would need $S_1$ to spell $ba$, but a lone $a$ can never terminate a derivation of $S$ (Step 1), so this is impossible. Only one split survives, so $abab$ has a unique parse tree and therefore a unique rightmost derivation, confirming option (C).
Step 4: Decidability check for option (D).
Any language produced by a context-free grammar sits inside the class of context-free languages, and every context-free language has a decision procedure for membership (CYK runs in polynomial time on the length of the input string). So it is never correct to call a CFG's language undecidable, and option (D) fails.
Step 5: Final answer.
$\[ \boxed{\text{(A), (B), (C) are true; (D) is false}} \]$
Was this answer helpful?
0
Top Questions on Context Free Grammars
- Consider the following context-free grammar \(G\).
\[ S \rightarrow abaABAbba \]\[ A \rightarrow aaBBAb \mid bBabaa \]\[ B \rightarrow aBb \mid ab \]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?- GATE CS - 2026
- Theory of Computation
- Context Free Grammars
- Want to practice more? Try solving extra ecology questions todayView All Questions
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems