Converting to Chomsky Normal form- derivations I'm attempting to convert the following grammar into Chomsky Normal Form:
$$S \to a S b S \mid b S a S \mid ε$$
I'm confused because in every example I've seen the grammar has been broken up into several productions (derivations?)-- Could someone show me how to do the derivations for this grammar?
My guess would be to replace the nonterminals (S) with terminals (a's or b's):
S--> aabb 
S--> ε
Thank you!
 A: A context free grammar is in CNF, if all rules are of the sort:


*

*$A \rightarrow XY$, where $A, X,Y$ are variables and $X, Y$ are not $S$.

*$A \rightarrow x$, where $x$ is Terminal and $A$ variable

*$S \rightarrow \varepsilon$
So let's look at your grammar:
$$ S \rightarrow aSbS \mid bSaS \mid \varepsilon $$
Step 1 Add a new start symbol $\overline{S}$:
\begin{align*}
\overline{S} &\rightarrow S \\
S &\rightarrow aSbS \mid bSaS \mid \varepsilon  
\end{align*}
Step 2 Eliminate productions $A \rightarrow \varepsilon$ (It was possible to derive the empty word from $S$ so we have to guarantee that the new grammar can do this too) : 
\begin{align*}
\overline{S} &\rightarrow S \mid \varepsilon \\
S &\rightarrow aSbS \mid bSaS \mid ab \mid ba \mid aSb \mid abS \mid bSa \mid baS
\end{align*}
Step 3 Eliminate production $A \rightarrow B$ by copy/paste:
\begin{align*}
\overline{S} &\rightarrow aSbS \mid bSaS \mid ab \mid ba \mid aSb \mid abS \mid bSa \mid ba \mid \varepsilon \\
S &\rightarrow aSbS \mid bSaS \mid ab \mid ba \mid aSb \mid abS \mid bSa \mid baS
\end{align*}
Step 4 Eliminate rules $A \rightarrow x_1 x_2 \dots x_n$ with more than two right sides by constructing $A\ \rightarrow x_1 X_1$, $X_1 \rightarrow x_2 X_2, \dots$, $X_{n-2} \rightarrow x_{n-1} x_n$:
\begin{align*}
\overline{S} &\rightarrow aX_1 \mid X_2 X_3 \mid ab \mid ba \mid aX_4 \mid aX_2 \mid bX_5 \mid ba \mid \varepsilon \\
S &\rightarrow aX_1 \mid X_2 X_3 \mid ab \mid ba \mid aX_4 \mid aX_2 \mid bX_5 \mid ba  \\
X_1 &\rightarrow SX_2\\
X_2 &\rightarrow bS\\
X_3 &\rightarrow aS\\
X_4 &\rightarrow Sb\\
X_5 &\rightarrow Sa
\end{align*}
Step 5 Now we eliminate rules like $A \rightarrow xB$ by rewriting them in $A \rightarrow V_x B$, $V_x \rightarrow x$:
\begin{align*}
\overline{S} &\rightarrow V_aX_1 \mid X_2 X_3 \mid V_aV_b \mid V_bV_a \mid V_aX_4 \mid V_aX_2 \mid V_bX_5 \mid V_bV_a \mid \varepsilon \\
S &\rightarrow V_aX_1 \mid X_2 X_3 \mid V_aV_b \mid V_bV_a \mid V_aX_4 \mid V_aX_2 \mid V_bX_5 \mid V_bV_a  \\
X_1 &\rightarrow SX_2\\
X_2 &\rightarrow V_bS\\
X_3 &\rightarrow V_aS\\
X_4 &\rightarrow SV_b\\
X_5 &\rightarrow SV_a\\
V_a &\rightarrow a\\
V_b &\rightarrow b
\end{align*}
This should be it. If you have any questions or if I did anything wrong please comment :)
