<p>The answer is much harder than one might think: <a href="https://arxiv.org/pdf/1201.2374.pdf" rel="nofollow noreferrer">this paper</a> contains a 50-page proof of an algorithm that does this.</p>
Convert PCFG to CNF: with null production rules
<p>There have been similar questions, like <a href="https://stackoverflow.com/q/27649735/2281318">this</a> or <a href="https://stackoverflow.com/questions/39850826/how-can-i-convert-pcfg-in-cnf-for-this-grammar">this</a>, but mine is different:</p>
<p>Let's say, I have a probabilistic context-free grammar (PCFG)</p>
<pre><code>S --&gt; A [1/2] | B [1/2]
A --&gt; eps [p] | AA [q] | x [r]
B --&gt; y [1]
</code></pre>
<p>where eps is an empty string, p + q + r = 1 (and q &lt;= 1/2, so that generating process finishes with probability 1).</p>
<ol>
<li>What is Chomsky normal form for this PCFG?</li>
</ol>
<p>I found it very difficult to get rid of the null production rule <code>A --&gt; eps</code> and at the same time keep all the probabilities of generating a given string intact. For example, <code>a := P(eps) = (1 - sqrt(1 - 4 p q)) / (2 q)</code> and <code>P(x) = r / (1 - 2 a q)</code> (as well as the others) should not be changed after creating a CNF(PCFG).</p>
<ol start="2">
<li>Is there a source for an algorithm that does a conversion PCFG --&gt; CNF(PCFG) for any PCFG? (<strong>or proves this is not possible</strong>)</li>
</ol>
<p>Searching for this, I found numerous sources, claiming that this is possible, however, I saw no proof for this.
Also, following the procedure for CNF(CFG) (where no probability is assigned to rules) does not work (or at least I do not see how one could generalize this to any PCFG).</p>
<hr />
<p>EDIT: <a href="https://cs.brown.edu/courses/csci1460/assets/files/parsing.pdf" rel="nofollow noreferrer">This pdf</a> (page 112) claims that <em>It
turns out that every epsilon-free PCFG G has a corresponding binarized
PCFG G′ that generates the same language as G</em>.</p>
<p>Binarized form of PCFG-s is slightly less restrictive than CFN. Again, the pdf provides no sources / proofs for this claim.</p>
<p>Epsilon free means that there are not rules <code>X --&gt; eps</code> (which is not true for the toy grammar above).</p>