GATE CSE 2024 | Set 1 | Question: 49

Question

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 1

For CNF, number of steps required is 2|w| - 1

Example: if
S -> AA
A -> a
for string 'aa' we will need 
S -> AA -> Aa -> aa         (Thus number of steps to derive string is 3)

Here the |w| = 90
Thus the number of derivations will be 2*90 - 1 = 179

Answer: 179

Comments

Given The Grammar Is In CNF, implies That it takes (2N-1) number of steps to derive the string (in CNF) ... where N = length of String ,

 

Hence , Here N = 90, So Answer Would be : 2(90) - 1 = 179