I'm having a hard time understanding conversion from CFG to CNF, I've tried multiple different ones but I can't get it to work. I'm trying to convert this one into a CNF.
$$ S \to aSBS \mid bSaS \mid \epsilon \\ B \to b \mid \epsilon $$
Now if I'm not completely mistaken I should first add a new start, like this: $$ S_0 \to S \\ S \to aSBS \mid bSaS \mid \epsilon \\ B \to b \mid \epsilon $$
By removing the null productions we get:
$$ S_0 \to S \mid \epsilon \\ S \to aSB \mid aBS \mid aB \mid aSS \mid a \mid aS \mid bSa \mid ba \mid bSaS \\ B \to b $$
Then we copy (?) this to to remove the unit production $S_0 \to S $
$$ S_0 \to aSB \mid aBS \mid aB \mid aSS \mid a \mid aS \mid bSa \mid ba \mid bSaS \mid \epsilon \\ S \to aSB \mid aBS \mid aB \mid aSS \mid a \mid aS \mid bSa \mid ba \mid bSaS \\ B \to b $$
But I honestly don't know what to do after this, the thing that I don't understand is what I should do with the $S \to a $ part? Should I create a new $ A \to a$?
$$ S_0 \to AC \mid AD \mid AB \mid AX \mid a \mid AS \mid DA \mid ba \mid DE \mid \epsilon \\ A \to a \\ B \to b \\ C \to SB \\ D \to BS \\ E \to AS \\ X \to SS \\ $$
This is what I came up with in the end, but I don't think it's alright. What about the a and ba in $ S_0$?
Taken from here, the following figure shows the definition of CNF:
Let's execute the following steps to convert the CFG to CNF:
(Assuming that there is a rule $A \to a$ that you have forgotten to include, otherwise no terminal symbols can be produced from the non-terminal A)
Add $S_0 \to S$ and Remove $B \to \epsilon$:
$S_0 \to S \\ S \to aSBS \mid bSaS \mid \epsilon \mid ASS \\ A \to a \\ B \to b$
Remove $S \to \epsilon$:
$S_0 \to S \mid \epsilon \\ S \to aSBS \mid bSaS \mid ASS \mid ABS \mid ASB \mid AB \mid bSa \mid baS \mid ba \mid AS \mid A \\ A \to a \\ B \to b$
Remove $S \to A$:
$S_0 \to S \mid \epsilon \\ S \to aSBS \mid bSaS \mid ASS \mid ABS \mid ASB \mid AB \mid bSa \mid baS \mid ba \mid AS \mid aABS\mid aSBA \mid aABA \mid bAaS \mid bSaA \mid bAaA \mid ASA \mid AAS \mid AAA \mid ABA \mid AAB \mid bAa \mid baA \mid AA \mid a\\ A \to a \\ B \to b$
Introduce additional rules such as $S_1 \to SS$, $S_2 \to BS$ etc. along with $A \to a$ and $B \to b$:
$S_0 \to S \mid \epsilon \\ S \to ASS_2 \mid BSS_6 \mid AS_1 \mid AS_2 \mid AS_3 \mid AB \mid BS_7 \mid BS_6 \mid BA \mid AS \mid AAS_2 \mid ASS_4 \mid BAS_4 \mid BAS_6 \mid BSS_8 \mid BAS_8 \mid AS_7 \mid AS_6 \mid AS_8 \mid AS_4 \mid AS_5 \mid BS_8 \mid AA \mid a\\ S_1 \to SS \\ S_2 \to BS \\ S_3 \to SB \\ S_4 \to BA \\ S_5 \to AB \\ S_6 \to AS \\ S_7 \to SA \\ S_8 \to AA \\ A \to a \\ B \to b$
Simplify once more with the rules introduced:
$S_0 \to S \mid \epsilon \\ S \to S_6S_2 \mid S_2S_6 \mid AS_1 \mid AS_2 \mid AS_3 \mid AB \mid BS_7 \mid BS_6 \mid BA \mid AS \mid S_8S_2 \mid S_6S_4 \mid S_4S_4 \mid S_4S_6 \mid S_2S_8 \mid S_4S_8 \mid AS_7 \mid AS_6 \mid AS_8 \mid AS_4 \mid AS_5 \mid BS_8 \mid AA \mid a\\ S_1 \to SS \\ S_2 \to BS \\ S_3 \to SB \\ S_4 \to BA \\ S_5 \to AB \\ S_6 \to AS \\ S_7 \to SA \\ S_8 \to AA \\ A \to a \\ B \to b$
Remove $S_0 \to S$:
$S_0 \to S_6S_2 \mid S_2S_6 \mid AS_1 \mid AS_2 \mid AS_3 \mid AB \mid BS_7 \mid BS_6 \mid BA \mid AS \mid S_8S_2 \mid S_6S_4 \mid S_4S_4 \mid S_4S_6 \mid S_2S_8 \mid S_4S_8 \mid AS_7 \mid AS_6 \mid AS_8 \mid AS_4 \mid AS_5 \mid BS_8 \mid AA \mid a \mid \epsilon \\ S \to S_6S_2 \mid S_2S_6 \mid AS_1 \mid AS_2 \mid AS_3 \mid AB \mid BS_7 \mid BS_6 \mid BA \mid AS \mid S_8S_2 \mid S_6S_4 \mid S_4S_4 \mid S_4S_6 \mid S_2S_8 \mid S_4S_8 \mid AS_7 \mid AS_6 \mid AS_8 \mid AS_4 \mid AS_5 \mid BS_8 \mid AA \mid a\\ S_1 \to SS \\ S_2 \to BS \\ S_3 \to SB \\ S_4 \to BA \\ S_5 \to AB \\ S_6 \to AS \\ S_7 \to SA \\ S_8 \to AA \\ A \to a \\ B \to b$
Obviously, there can be more efficient ways, but using the above steps too, we could obtain a CNF from the CFG.