Help convert the following CFG into an equivalent CFG in Cho

Help convert the following CFG into an equivalent CFG in Chomsky normal form.

Theorem 2.9 goes as follows:

Solution

Let us consider new start variable A0 and the new rule A0 A, which gives

A0 A

A BAB | B |

B 00 |

Then we remove rules:

Removing B yields

A0 A

A BAB | BA | AB | A | B |

B 00

Removing A yields

A0 A |

A BAB | BA | AB | A | B | BB

B 00

We don’t need to remove the -rule A0 as A0 is the start variable and that is allowed in Chomsky normal form.

Then we remove unit rules:

Removing A A yields

A0 A |

A BAB | BA | AB | B | BB

B 00

Removing A B yields

A0 A |

A BAB | BA | AB | 00 | BB

B 00

Removing A0 A gives

A0 BAB | BA | AB | 00 | BB |

A BAB | BA | AB | 00 | BB

B 00

Now we replaced ill-placed terminals 0 by variable U with new rule U 0, which gives

A0 BAB | BA | AB | UU | BB |

A BAB | BA | AB | UU | BB

B UU

U 0

Now we make it short by using the rules with a long RHS to a sequence of RHS’s with only 2 variables each. Hence the rule A0 BAB is replaced by the 2 rules A0 BS1 and S1 AB.

Also the rule A BAB is replaced by the 2 rules A BS2 and S2 AB.

Thus, our nal CFG in Chomsky normal form is

A0 BS1 | BA | AB | UU | BB |

A BS2 | BA | AB | UU | BB

B UU

U 0

S1 AB

S2 AB

The CFG in Chomsky normal form is G = (V, , R, A0), where

The set of variables is V = {A0, A, B, U, S1, S2}, the start variable is A0, the set

of terminals is = {0}.