GATE CS 1992 Q02 — Parsing (LL, LR)

A Context-Free Grammar (CFG) in Chomsky Normal Form (CNF) has production rules restricted to the following forms:

1. $A \rightarrow BC$ (where $B$ and $C$ are non-terminals)
2. $A \rightarrow a$ (where $a$ is a terminal)

Let $w$ be a string of length $l$ ($l \ge 1$) derived from the start symbol $S$. We can determine the number of steps in the derivation as follows:

• Step 1: Generating $l$ non-terminals
  We start with a single non-terminal (the start symbol $S$). Each application of a production rule of the form $A \rightarrow BC$ replaces one non-terminal with two, thereby increasing the total number of symbols in the sentential form by exactly $1$.
  To grow the sentential form from $1$ symbol to $l$ non-terminals, we must apply these rules exactly: $$\text{Number of branching steps} = l - 1$$
• Step 2: Converting non-terminals to terminals
  Once we have a sentential form consisting of $l$ non-terminals, we must replace each non-terminal with a terminal using rules of the form $A \rightarrow a$. Since there are $l$ non-terminals, this requires exactly $l$ steps: $$\text{Number of terminal substitution steps} = l$$

Adding these together, the total length of the derivation is:

Example:
For a string of length $l = 2$ (e.g., $ab$):

1. $S \rightarrow AB$ (1 step)
2. $A \rightarrow a$ (2 steps)
3. $B \rightarrow b$ (3 steps)