GATE 2024 CS (CS1) – Question 59
Let $G=(V,\Sigma,S,P)$ be a context-free grammar in Chomsky Normal Form with $\Sigma=\{a,b,c\}$ and $V$ containing 10 variable symbols including the start symbol $S$. The string $w=a^{30}b^{30}c^{30}$ is derivable from $S$. The number of steps (application of rules) in the derivation $S\to^* w$ is _________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 179
Explanation
In CNF, deriving a string of length n takes exactly 2n−1 steps: n−1 binary rule applications plus n terminal rules. With n=90, steps = 2·90−1 = 179.