GATE CS 2024 Set 1 — Question 59

NAT+2 / -0MediumParse Trees & DerivationsContext-Free LanguagesTheory of ComputationChomsky Normal Form

Theory of Computation → Context-Free Languages → Chomsky Normal Form

Last updated 20 August 2026

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 _________

179 to 179

In a Context-Free Grammar (CFG) in Chomsky Normal Form (CNF), every production is of the form A → BC or

A \rightarrow a

, where

A, B, C \in V

and

a \in \Sigma

To derive a string of length

n

1.We need

n-1

applications of rules of the form A → BC to generate a sentential form with

n

variables. Starting from the start symbol

S

(1 variable), each such rule application increases the number of variables by exactly 1. Thus, to reach

n

variables, we need

n-1

steps.

2.We need

n

applications of rules of the form

A \rightarrow a

to replace each of the

n

variables with a terminal symbol from

\Sigma

Total number of steps =

(n-1) + n = 2n - 1

Given the string

w = a^{30}b^{30}c^{30}

, its length

n = 30 + 30 + 30 = 90

Number of steps =

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

Note: The total number of variables in

V

(which is 10) is irrelevant to the number of steps in the derivation of a specific string.