# Chomsky normal form complexity

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

• 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. – Joe Tait Jun 13 '14 at 22:02

## 1 Answer

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

• 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)$ ? – user156981 Jun 13 '14 at 22:11
• 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. – mlk Jun 13 '14 at 22:19
• 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)$ ? – user156981 Jun 13 '14 at 22:23