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