# Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

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$.

• @justin This is a typical question that can be interesting but was formulated in a poor way (hence the downvotes). As Yuval Filmus expressed, you should edit your answer so that it reflects your question more properly (e.g. This article says this about that and I understand this aspect [you understand where the $2n$ comes from] because of this & that ["since there are only 2 variables on the R.H.S (...)"] but I don't understand this specific aspect [the $-1$ part.]). In short: while you made your problem clear, you didn't show any effort to explain what you understood and what you didn't. – Auberon Mar 29 '16 at 17:31
• @Auberon. I upvoted your comment (FWIW), but I must confess that it took me a while to check that the delimiters were properly nested: "...properly (e.g., [my note, the comma should be here] ... [...] ... [... (...)] ... [...])". Yup, this Dyck language sample is legitimate. [insert grinning emoticon here.] – Rick Decker Apr 5 '16 at 0:22

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.

• :Could you tell why we use $n−1$ rules of the form $A \to BC$. – justin Mar 29 '16 at 9:23
• @justin Added an example to my answer. – Auberon Mar 29 '16 at 17:23
• :Could you tell how the length of string becomes 1 in the first step. – justin Mar 30 '16 at 6:20
• @justin $S$ isn't a rule, it's a symbol... And you start every derivation with it. You take $S$ and then you apply your first rule of form $S /to AB$. So when you only have $S$, you haven't applied any rules yet. – Auberon Mar 31 '16 at 15:53
• @OmarHossamAhmed Then it means there is no string of length $n$ in the language generated by the grammar, or at least you've used the wrong non-terminal rules. – Auberon Nov 6 '18 at 10:46

And each of the $A \to B C$ produtions make the sentential form one longer. You start with length $1$, to reach $n$ means $n - 1$ steps. If a string has length $n$, there will be $n$ steps to get the terminals. In all, $2 n - 1$ steps.

• :Do you mean to say that the start symbol is of length 1? – justin Mar 29 '16 at 6:46
• @justin Yes, he does. – Auberon Mar 29 '16 at 17:20

Let us consider an simple example.

A -> BC
B -> b
C -> c


String to be generated is bc.

Then the steps are.

A -> BC
-> bC
-> bc


Thus no of steps required is 3. That is $$2n-1$$.