Conversion from Context Free Grammar to Chomsky Normal Form :
(I ll tell you the steps and will also solve the example you asked simultaneously)
Step 1 : Introduce New Non-terminal $S_0$ and make it derive the start variable which is S
Thus
$S_0$ -> S
S -> ASA | aB
A -> B | S
B -> b | $\varepsilon$
Step 2 : Eliminate all $\varepsilon$ transitions
THus we need to eliminate B -> $\varepsilon$
For this we must to replace B with $\varepsilon$ in RHS of every production having B
THus we get,
$S_0$ -> S
S -> ASA | aB | a
A -> B | S | $\varepsilon$
B -> b
Now new $\varepsilon$ transition is introduced which is A -> $\varepsilon$ .. thus we need to eliminate it too
$S_0$ -> S
S -> ASA | aB | a | SA | AS | S ... Note: S -> S can be ignored
A -> B | S
B -> b
Step 3 : Eliminate all Unit transitions i.e. those productions having exactly one non-terminal in RHS .
thus we need to eliminate A -> B , A->S ,$S_0$ -> S
THus,first removing A-> B
$S_0$ -> S
S -> ASA | aB | a | SA | AS
A -> b | S
B -> b
NOw removing A-> S
$S_0$ -> S
S -> ASA | aB | a | SA | AS
A -> b | ASA | aB | a | SA | AS
B -> b
NOw removing $S_0$ -> S
$S_0$ -> ASA | aB | a | SA | AS
S -> ASA | aB | a | SA | AS
A -> b | ASA | aB | a | SA | AS
B -> b
Step 4 : Now eliminate all the productions that are non in CNF
$S_0$ -> AM | NB | a | SA | AS
S -> AM | NB | a | SA | AS
A -> b | AM | NB | a | SA | AS
B -> b
M -> SA
N-> a
The above CFG is in CNF .
:)
HINT: There are two slightly different definitions of Chomsky normal form. It appears that you’re using the one that simply requires each production to be of the form $X\to YZ$ or $X\to a$, rather than the one in Wikipedia; this causes no problems, since the lack of $\lambda$-productions means that $\lambda$ isn’t in the language anyway.
The algorithm given in that article for converting $G$ to $G'$ still works; we’re just in the fortunate situation of being able to ignore parts of it as not applicable. $G$ has no $\lambda$-productions or unit productions, and your definition of Chomsky normal form doesn’t require elimination of the initial symbol from the righthand side (the START step), so the last two steps, DEL and UNIT, don’t arise, and we need only perform the TERM and BIN steps.
- Show that the TERM step adds at most $|T|$ productions to the grammar.
After the TERM step has been completed, every production is of one of two kinds: $X\to a$ (where $X$ might be one of the new non-terminals introduced in the TERM step), or $X\to Y_1\ldots Y_n$, where $n\ge 2$. Productions of the form $X\to Y_1Y_2$ are fine, but we have to get rid of the ones with $n\ge 3$.
- Show that the procedure used in the BIN step replaces a production $X\to Y_1\ldots Y_n$ with $n-1$ productions of the form $Z\to UV$.
- Conclude that $G'$ has at most $|T|+(K-1)|P|$ productions.
If you were using the definition of Chomsky normal form given in the Wikipedia article, the grammar with initial symbol $S$, terminal symbols $a$ and $b$, and productions $S\to Sa\mid bb$ would be a counterexample to the theorem. Clearly $|P|=|T|=K=2$, so $(K-1)|P|+|T|=4$. However, the smallest equivalent grammar in (this version of) Chomsky normal form has six productions:
$$\begin{align*}
&S\to BB\mid XA\\
&X\to BB\mid XA\\
&A\to a\\
&B\to b
\end{align*}$$
If we allow $S$ to appear on the righthand side, we can reduce this to four, as in the theorem:
$$\begin{align*}
&S\to BB\mid SA\\
&A\to a\\
&B\to b
\end{align*}$$
Best Answer
What you have isn’t in Chomsky normal form: the productions $S\to aS$, $S\to aA_0$, and $A\to aA$ don’t meet the requirements. After removing the $\lambda$ production you should have
$$\begin{align*} &S\to aS\mid aA\mid a\mid bB\\ &A\to aA\mid a\\ &B\to bB\mid aaB \end{align*}$$
This has no unit productions, but the only productions that are compatible with Chomsky normal form are $S\to a$ and $A\to a$, so the others have to be cleaned up. Introduce new non-terminals $A_0$ and $B_0$ together with productions $A_0\to a$ and $B_0\to b$, and replace $a$ and $b$ in non-terminal productions by $A_0$ and $B_0$, respectively, to get this equivalent grammar:
$$\begin{align*} &S\to A_0S\mid A_0A\mid a\mid B_0B\\ &A\to A_0A\mid a\\ &B\to B_0B\mid A_0A_0B\\ &A_0\to a\\ &B_0\to b \end{align*}$$
This has two productions that are incompatible with Chomsky normal form, $S\to A_0S$ and $B\to A_0A_0B$: the former is bad because the initial symbol appears on the righthand side, and the latter is bad because the righthand side is too long. The first problem is fixed by adding a new non-terminal $S_0$, making it the initial symbol, and adding the production $S_0\to S$. The second is fixed by adding a new non-terminal $X$, replacing the production $B\to A_0A_0B$ with $B\to A_0X$, and adding the production $X\to A_0A_0$. The result is the following grammar in Chomsky normal form:
$$\begin{align*} &S_0\to S\\ &S\to A_0S\mid A_0A\mid a\mid B_0B\\ &A\to A_0A\mid a\\ &B\to B_0B\mid A_0X\\ &X\to A_0B\\ &A_0\to a\\ &B_0\to b \end{align*}$$