I have a grammar that has the following productions:
$S\to aSbb$, $S\to aSa$ and $S\to c$
I am supposed to convert this grammar to normal form where the productions have to be as follows:
$A\to aB$ where $AB\in V$ and $a\in \Sigma$
$A\to Ba$ where $AB\in V$ and $a\in \Sigma$
$A\to \epsilon$
I have gotten some way, but I struggle with the fact that it seems that the number of $b$'s has to be even.
Eliminate $S$ from RHS: Replace the start symbol by $S_{0}$; the grammar becomes:
\begin{align} & S_{0} \to S \\ & S \to aSbb \mid aSa \mid c \end{align}
Eliminate RHS with more than one non terminal: Begin by replacing $S \to aSbb$ with:
\begin{align} &S \to aA \\ &A \to Bb \\ &B \to Sb \\ \end{align}
The grammar thus becomes:
\begin{align} &S_{0} \to S \\ &S \to aA \mid aSa \mid c \\ &A \to Bb \\ &B \to Sb \\ \end{align}
And then, replace $aSa$ by:
\begin{align} &S \to aC\\ &C \to Sa\\ \end{align}
Leaving us with grammar:
\begin{align} &S_{0} \to S\\ &S \to aA \mid aC \mid c\\ &A \to Bb\\ &B \to Sb\\ &C \to Sa\\ \end{align}
Eliminate unit productions: The final grammar comes by replacing $S \to c$:
\begin{align} &S_{0} \to S\\ &S \to aA \mid aC \mid Dc\\ &A \to Bb\\ &B \to Sb\\ &C \to Sa\\ &D \to \epsilon \\ \end{align}