GATE CSE 2024 Session 1 Q59: Derivation length for a 90-symbol string in Chomsky Normal Form

Theory of Computation
2 marks
NAT
No negative marking

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 \overset{*}{\Rightarrow} w$ is _________

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 179 (official GATE 2024 final answer key)

Concept used: In CNF a string of length $n \ge 1$ needs exactly $2n - 1$ rule applications.

First step: Count $n - 1$ applications of $A \to BC$ and $n$ of $A \to a$ , with $n = 90$ .

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 Session 1 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2024 Session 1 questions →

GATE CSE 2024 Session 1 Q59: Derivation length for a 90-symbol string in Chomsky Normal Form

Question

Full step-by-step solution

More Theory of Computation PYQs