Converting to Chomsky Normal form- derivations

Question

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!

Answer 1

A context free grammar is in CNF, if all rules are of the sort:

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

2. $A \rightarrow x$, where $x$ is Terminal and $A$ variable

3. $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 :)