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 \rightarrow^{*} w\) is _________
Answer
179
Explanation
In Chomsky Normal Form every rule has the form \(A \rightarrow BC\) or \(A \rightarrow a\), and \(|w| = 90\).
- Each \(A \rightarrow BC\) step adds one symbol to the sentential form. Growing from the single symbol \(S\) to 90 symbols takes exactly 89 such steps.
- Each \(A \rightarrow a\) step turns one variable into one terminal, and every one of the 90 terminals is produced this way: 90 steps.
The derivation therefore has \(89 + 90 = 179\) steps. In general a CNF derivation of a string of length \(n \ge 1\) takes \(2n - 1\) steps; the 10 variables do not affect the count.
Answer: 179