title: Convert a CFG into CNF
body: <p>I'm still new to <code>CFG and CNF</code> and have trouble sometimes understanding the concepts.</p>
  
  <p>I'm trying to convert this CFG into Chomsky Normal Form: </p>
  
  <pre><code>G: S -&gt; aSbS | bSaS | epsilon
  </code></pre>
  
  <p>I think the language generates all strings with same number of a and b, i.e. <code>{a^n b^n |n&gt;-0}</code>.</p>
  
  <p>But to convert it into CNF, I've finished adding a new start state and eliminating epsilon-productions:</p>
  
  <pre><code>S_0 -&gt; S | epsilon
  S -&gt; aSbS | bSaS | aS | bS | a | b
  </code></pre>
  
  <p>Perhaps I need two non-terminals(variables) A -> a and B -> b :</p>
  
  <pre><code>S_0 -&gt; S | epsilon
  S -&gt; ASBS | BSAS | AS | BS | a | b
  A -&gt; a
  B -&gt; b
  </code></pre>
  
  <p>I'm stuck here and really don't know what the next step should be. There seem to be no unit productions or useless symbols.</p>