Project ForgeLet 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³⁰b³⁰c³⁰ is derivable from S. The number of steps (application of rules) in the derivation S→*w is ____.
Explanation
In CNF, every rule is either A→BC (a binary branch, increasing the total symbol count by 1) or A→a (a terminal-producing step, converting one variable to one terminal, not changing count). For a derived string of length n, the derivation needs exactly n−1 binary-branching steps (to grow from 1 symbol to n symbols) plus n terminal-producing steps (one per final terminal) = 2n−1 total steps. Here n=90 (30+30+30), so steps = 2(90)−1 = 179.
Source: GATE CS 2024 (Session 1 / CS1) (2024)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.