# How to put the given context-free grammar into Chomsky Normal Form?

I have questions about how to put the grammar below in CNF - Chomsky Normal Form:

S ->aAa | bBb | ВВ;

A -> C;

B -> S | A;

C -> S | ε;

I did it like this:

1. I eliminated empty productions:

S ->aAa | aa | bBb | bb| ВВ;

A -> C;

B -> S | A;

C -> S;

1. I eliminated unit productions:

S ->aAa | aa | bBb | bb | ВВ;

A -> aAa | aa | bBb | bb | ВВ;

B -> Aa | aa | bBb | bb | ВВ;

C -> Aa | aa | bBb | bb | ВВ;

1. I eliminated the useless variables (C), but it only becomes inaccessible after removing the unitary production of A ->C). Can anyone help me and tell me if this is right?

It is the case that $$C$$ becomes inaccessible, but your grammar isn't in normal form (yet). Rules like $$S \to aAa$$ or $$S \to bb$$ aren't allowed in CNF.

Also your grammar isn't equal to the original, since you forgot that $$S$$ is nullable when removing the $$\varepsilon$$ production (e.g. you could derive $$S \Rightarrow BB \Rightarrow^* AA \Rightarrow^* CC \Rightarrow^* \varepsilon$$ which isn't possible in your last grammar).

When bringing a grammar in CNF it's often a good idea to remove all $$A \to B$$ transitions first, and then remove the $$\varepsilon$$ transitions. So first start off by adding a new start variable $$S'$$

$$S \to S'$$ $$S' \to aAa | bBb | BB$$ $$A \to C$$ $$B \to S' | A$$ $$C \to S' | \varepsilon$$

then remove the $$A \to C$$ and $$B \to A$$ transition

$$S \to S'$$ $$S' \to aAa | bBb | BB$$ $$A \to S' | \varepsilon$$ $$B \to S' | \varepsilon$$

$$C$$ is now inaccessible, so we'll ignore it. Remove $$A \to S'$$ and $$B \to S'$$

$$S \to S'$$ $$S' \to aAa | aS'a | bBb | bS'b | BB | S'B | BS' | S'S'$$ $$A \to \varepsilon$$ $$B \to \varepsilon$$

remove the $$\varepsilon$$ transitions

$$S \to S' | \varepsilon$$ $$S' \to aa | aS'a | bb | bS'b | S' | S'S' | \varepsilon$$

remove $$S' \to \varepsilon$$ and $$S' \to S'$$

$$S \to S' | \varepsilon$$ $$S' \to aa | aS'a | bb | bS'b | S'S'.$$

This can now be brought into CNF

$$S \to S' | \varepsilon$$ $$S' \to AA | AX | BB | BY | S'S'$$ $$A \to a$$ $$X \to S'A$$ $$B \to B$$ $$Y \to S'B$$

as you should verify :]