How to prove that the complexity of transforming any context-free grammar without epsilon productions to chomsky normal form is $ O(N^2) $ , because I found this in 2 articles, but without proof

  • 1
    $\begingroup$ Welcome to maths.stackexchange! It might be useful to give some extra context, such as the articles that mention this, or any attempts you have made at proving the statement. $\endgroup$ – Joe Tait Jun 13 '14 at 22:02

As far as I know, this is textbook stuff so the proofs are obviously not found in articles. However if I remember correctly, you get to Chomsky normal form by first replacing any terminals in something like $$A \rightarrow BCst$$

by some extra nonterminal symbols

$$A \rightarrow BCST$$ $$S \rightarrow s$$ $$T \rightarrow t$$

and then in the second step you replace longer rules like

$$A\rightarrow BCD$$

with again additional nonterminals

$$A\rightarrow BA'$$ $$A'\rightarrow CD$$

I think it is easy to see that each replacement step only needs $O(n)$ of work per rule, so you end up with $O(n^2)$, since the number of rules is clearly bounded by $n$.

  • $\begingroup$ n is the number of productions ? I don't understand it correctly. We have N productions , so why replacement for each production needs $ O(n) $ ? $\endgroup$ – user156981 Jun 13 '14 at 22:11
  • $\begingroup$ n usually is some size representing the encoding of the grammar. There may be a huge number of productions (still bounded by n) or a production giving a huge number of symbols (again bounded by n), we need to account for both. $\endgroup$ – mlk Jun 13 '14 at 22:19
  • $\begingroup$ so, let's assume that n is number of productions. If all productions is A -> X , where length of X is constant C , so we need for each production (C-1) replacement and the overall complexity will be n(C-1) assuming that we changed all terminals to nonterminals. C is constant, so $ O(n) $ ? $\endgroup$ – user156981 Jun 13 '14 at 22:23

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.