5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ When I read about this, I proved it by induction. $\endgroup$ – Auberon Mar 22 '16 at 11:58
  • 3
    $\begingroup$ @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. $\endgroup$ – Auberon Mar 29 '16 at 17:31
  • 1
    $\begingroup$ @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.] $\endgroup$ – Rick Decker Apr 5 '16 at 0:22
6
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ :Could you tell why we use $n−1$ rules of the form $A \to BC$. $\endgroup$ – justin Mar 29 '16 at 9:23
  • $\begingroup$ @justin Added an example to my answer. $\endgroup$ – Auberon Mar 29 '16 at 17:23
  • $\begingroup$ :Could you tell how the length of string becomes 1 in the first step. $\endgroup$ – justin Mar 30 '16 at 6:20
  • 1
    $\begingroup$ @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. $\endgroup$ – Auberon Mar 31 '16 at 15:53
  • 1
    $\begingroup$ @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. $\endgroup$ – Auberon Nov 6 '18 at 10:46
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ :Do you mean to say that the start symbol is of length 1? $\endgroup$ – justin Mar 29 '16 at 6:46
  • $\begingroup$ @justin Yes, he does. $\endgroup$ – Auberon Mar 29 '16 at 17:20
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.