First, simplify the context-free grammar, and then convert the grammar to Chomsky normal form and Greibach normal form.

1)

S --> AB | aB

A --> abb |

B --> bbA

2)

S --> baAB

A --> bAB |

B --> BAa | A |

Supplemental Information:

a) Algorithm to Convert into Chomsky Normal Form

Step 1 If the start symbol S occurs on some right side, create a new start symbol S and a new production S S.

Step 2 Remove Null productions. (Using the Null production removal algorithm discussed earlier)

Step 3 Remove unit productions. (Using the Unit production removal algorithm discussed earlier)

Step 4 Replace each production A B₁B_n where n > 2 with A B₁C where C B₂ B_n. Repeat this step for all productions having two or more symbols in the right side.

Step 5 If the right side of any production is in the form A aB where a is a terminal and A, B are non-terminal, then the production is replaced by A XB and X a. Repeat this step for every production which is in the form A aB.

b) Algorithm to Convert a CFG into Greibach Normal Form

Step 1 If the start symbol S occurs on some right side, create a new start symbol S and a new production S S.

Step 2 Remove Null productions. (Using the Null production removal algorithm discussed earlier)

Step 3 Remove unit productions. (Using the Unit production removal algorithm discussed earlier)

Step 4 Remove all direct and indirect left-recursion.

Step 5 Do proper substitutions of productions to convert it into the proper form of GNF.