GATE CS 2024 Set 1 Q49 — Parsing (LL, LR)

In a Context-Free Grammar (CFG) in Chomsky Normal Form (CNF), all production rules must be of one of the following forms:

1. $A \rightarrow BC$ (where $B, C$ are variables)
2. $A \rightarrow a$ (where $a$ is a terminal)

To derive a string $w$ of length $n$ ($n \ge 1$) from the start symbol $S$:

• We start with $1$ variable ($S$).
• Each application of a production of the form $A \rightarrow BC$ increases the number of variables in the sentential form by exactly $1$. To reach a sentential form containing $n$ variables, we need exactly $n - 1$ steps.
• Each of these $n$ variables must then be replaced by a terminal using a production of the form $A \rightarrow a$. This requires exactly $n$ steps.

Thus, the total number of steps (rule applications) in the derivation of any string of length $n$ is:

$$\text{Total steps} = (n - 1) + n = 2n - 1$$

For the given string $w = a^{30} b^{30} c^{30}$, the length of the string is:

$$n = |w| = 30 + 30 + 30 = 90$$

Substituting $n = 90$ into the formula:

$$\text{Number of steps} = 2(90) - 1 = 180 - 1 = 179$$

Note: The number of variable symbols (10) is extra information and does not affect the number of derivation steps.