Question

Show that if G is a CFG in Chomsky normal form, then for any string w is a member of L(G) of length n >=1, exactly 2n-1 steps are required for any derivation of w.

Answer 1

To Show that exactly 2n-1 steps will be required we begin with a start variable or the single non-terminal ("S") and form the string w by making substitutions, according to the rules of normal form. Each rule of the form A to BC (A->BC) adds a new non-terminal, and each rule of the form A to a (A->a) converts one non-terminal into a terminal. Since it takes (n-1) steps to grow our string from the original non-terminal to n non-terminals because the first terminal is given hence n-1 steps are required to reach to n non-terminals, and then n steps to convert each of those non-terminals into terminals as in the form of converting non-terminals to terminals whole n steps have to be undertaken, it takes 2n-1 steps to derive a string of length n (n-1+n = 2n-1).