How do I convert to Chomsky Normal Form(CNF)

Question

How do I convert below grammar to CNF?

S → ASA | aB

A → B | S

B → b | ε

Answer 1

We can split the transformation of context free grammars to Chomsky Normal Form into four steps.

1. The Bin step ensures that all alternatives in all productions contains no more than two terminals or non-terminals.
2. The Del step "deletes" all empty string tokens.
3. The Unit steps "inlines" productions that directly map to a single non-terminal.
4. The Term step makes sure terminals and non-terminals are not mixed in any alternative.

From your example, describing each step, the transformation to CNF can look like the following.

Bin

Alternatives in production S is split up into smaller productions. New non-terminals are T.

S → AT | aB
A → B | S
B → b | ε
T → SA

Del

From the production of S, nullable non-terminals A and B were factored out.

S → AT | T | aB | a
A → B | S
B → b | ε
T → SA

For the production of A, no action need be taken.

S → AT | T | aB | a
A → B | S
B → b | ε
T → SA

From the production of B, empty string tokens were removed.

S → AT | T | aB | a
A → B | S
B → b
T → SA

From the production of T, nullable non-terminal A were factored out.

S → AT | T | aB | a
A → B | S
B → b
T → SA | S

Unit

"Inlined" the production for B in A.

S → AT | T | aB | a
A → b | S
B → b
T → SA | S

Term

Replaced a terminal "a" in production S with the new non-terminal U.

S → AT | T | UB | a
A → b | S
B → b
T → SA | S
U → a

And you're done.