GATE 2024 CS1 Q.59: solution and answer

GATE 2024 · CS1Q.59 · 2 marks · NAT

Let $G = (V, Σ, S, P)$ be a context-free grammar in Chomsky Normal Form with $Σ = {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 \to^{*} w$ is ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The derivation takes 179 steps.

Official answer: 179Source: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

In Chomsky Normal Form every production is either $A \to B C$ (two variables) or $A \to a$ (one terminal).
The string has length $∣ w ∣ = 30 + 30 + 30 = 90$ .
Each rule $A \to a$ adds one terminal and no other symbol is ever turned into a terminal. So exactly $90$ rules of this kind are used, one for each terminal of $w$ .
Each rule $A \to B C$ replaces one symbol by two, so it raises the length of the sentential form by exactly $1$ . Rules $A \to a$ leave the length unchanged. We start from the single symbol $S$ (length $1$ ) and end at length $90$ , so exactly $90 - 1 = 89$ rules of the form $A \to B C$ are used.
Total number of steps $= 89 + 90 = 2∣ w ∣ - 1 = 2 \times 90 - 1 = 179$ .
The count depends only on $∣ w ∣$ . The number of variables (10) and the particular derivation do not change it.

KEY IDEA

In a CNF grammar, deriving a string of length $n$ always takes exactly $n - 1$ rules $A \to B C$ and $n$ rules $A \to a$ , so $2 n - 1$ steps in all.

WATCH OUT FOR

Counting only the $89$ binary rules, or only the $90$ terminal rules. Another slip is trying to use the number of variables (10) or the shape $a^{30} b^{30} c^{30}$ , neither of which affects the count.

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 9 CFG & PDA questions, with notes

GATE 2024 CS1 Q.59: solution and answer

Answer and solution

More CFG & PDA questions