[Solved]: Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

Problem Detail: 

I would like to know how they obtained the expression $2n-1$ as said from the excerpt of article (p.3):

The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters has exactly 2n−1 steps.

I could get how $2n$ comes since there are only 2 variables on the R.H.S of each production but couldn't get how the expression $−1$ came in $2n−1$.

Asked By : justin

Answered By : Auberon

Let $n$ be the length of a string. We start with the (non-terminal) symbol $S$ which has length $n=1$.

Using $n - 1$ rules of form $(non-terminal) \rightarrow (non-terminal)(non-terminal)$ we can construct a string containing $n$ non-terminal symbols.

Then on each non-terminal symbol of said string of length $n$ we apply a rule of form $(non-terminal) \rightarrow (terminal)$. i.e. we apply $n$ rules.

In total we will have applied $n - 1 + n = 2n - 1$ rules.

example

Observe following grammar in Chomsky-normal form.

$ \begin{align} S & \to AB \\ A & \to BC | AC\\ A & \to h|b\\ B & \to a \\ C & \to z \\ \end{align} $

Consider following derivation

$ \begin{align} \text{Current string} & & \text{rule applied} & & \text{#rules applied} & & \text{#length of string} \\ S & & \text{\\} & & 0 & & 1 \\ AB & & S \to AB & & 1 & & 2 \\ BCB & & A \to BC & & 2 & & 3 \\ \vdots & & \vdots & & \vdots & & \vdots \\ A\cdots CB & & \text{[multiple rules]} & & n-1 & & n \end{align} $

This last line represents a string containing only non-terminals. You can see that a string containing $n$ non-terminals is derived using $n-1$ rules. Let's continue. Applying $n$ rules of form $A \to a$ to each non-terminal in the string above gives you a string containing only terminals and thus a string from the language decided by the grammar. The length of the string has not changed (it's still $n$) but we applied an additional $n$ rules so in total we have applied $n-1 + n = 2n - 1$ rules.

While this explanation hopefully gives you an intuitive understanding, I think it would be an useful excercise to construct a formal proof using induction.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54775

3.2K people like this

 Download Related Notes/Documents