2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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 :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.