Let 𝐺 = (𝑉, Σ, 𝑆, 𝑃) be a context-free grammar in Chomsky Normal Form with…

Key insight: in a Chomsky Normal Form derivation each application of a rule either replaces one variable by two variables (A → BC) or replaces one variable by a terminal (A → a).

• Let n be the length of the derived string. Each terminal in the final string requires exactly one application of a rule of the form A → a, so the number of terminal-rule applications is n.

• Let x be the number of binary-rule applications A → BC. Starting from one variable (the start symbol), each binary rule increases the current number of variables by 1, and each terminal rule decreases it by 1. To end with zero variables, we need x − n = −1, so x = n − 1.

• Total number of rule applications = (number of binary rules) + (number of terminal rules) = (n − 1) + n = 2n − 1.

Apply this to the given string of length 30 + 30 + 30 = 90: total steps = 2·90 − 1 = 179.