GATE CS 2024 Set 1 Q.59: Context-Free Grammars, Pushdown Automata and CFLs

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 _________

Your answer

Official answer and solution

Official answer: 179
From: Official GATE 2024 answer key

Solution

Use the property that deriving any string of length $n \ge 1$ in a Chomsky Normal Form (CNF) grammar requires $2n - 1$ production steps.

In Chomsky Normal Form (CNF), every production is either of the form $A \rightarrow BC$ (which increases the number of variables in the sentential form by $1$ ) or $A \rightarrow a$ (which replaces $1$ variable with $1$ terminal). To derive a string $w$ of length $n = |w| \ge 1$ :

Exactly $n - 1$ steps of type $A \rightarrow BC$ are used to expand $S$ into $n$ variables.
Exactly $n$ steps of type $A \rightarrow a$ are used to convert those $n$ variables into terminals.

Here $w = a^{30}b^{30}c^{30}$ has length $n = 30 + 30 + 30 = 90$ . Therefore, the total number of derivation steps is:

2n - 1 = 2(90) - 1 = 179

Final answer

179

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 1 (CS1)
Question: 59 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source