Sipser Exercise 2.26

Theorem: If a grammar is in Chomsky normal form, for any string of length with , any derivation of has steps.


Proof: Let with . To generate , we must first generate a string with exactly variables, since terminals are only introduced as the replacement of exactly one variable. A string with variables must be generated through a derivation of steps. To see this, note that the start variable is a string containing one variable, and one derivation step always replaces one variable with exactly two variables, that is, increases the amount of variables by 1. So After derivations, we will have a string with variables. After generating the string of variables, we must replace each variable with a terminal, which requires more derivations. So a derivation of requires steps.