chomsky normal form

Question

A CFG  is said to be in chomsky normal form  if all the production are of form A->BC or A->a .let G be a CFG in CNF .To derive a string of length x , the no of production to be used is

a)2x-1 b)2x  c)2x+1  d)2^x

Answer 1

Option a http://bsd7.cs.sunysb.edu/~stark/CSE540/Handouts/hw2_notes.pdf

Answer 2

I think more appropriate question would be 'number of steps' rather than number of 'productions'

 

To derive $x$ terminals we need $x$ non terminals. The $x$ non terminals can be derived as -

$<non-terminal> \rightarrow <non-terminal> <non-terminal>$

in $x-1$ steps as in the above production type every non terminal consumes one symbol at LHS and produces two non-terminals at RHS in each step except the first step where LHS is starting symbol.

The $x$ terminals from $x$ non terminals can be derived using -

$<non-terminal> \rightarrow <terminal>$

in $x$ steps

Hence total steps are $2x - 1$