Conversion to Chomsky Normal Form

Question

I do need your help. I have these productions:

1) A--> aAb
2) A--> bAa
3) A--> ε

I should apply the Chomsky Normal Form (CNF).

In order to apply the above rule I should:

1. eliminate ε producions
2. eliminate unitary productions
3. remove useless symbols

Immediately I get stuck. The reason is that A is a nullable symbol (ε is part of its body)

Of course I can't remove the A symbol.

Can anyone help me to get the final solution?

Answer 1

As the Wikipedia notes, there are two definitions of Chomsky Normal Form, which differ in the treatment of ε productions. You will have to pick the one where these are allowed, as otherwise you will never get an equivalent grammar: your grammar produces the empty string, while a CNF grammar following the other definition isn't capable of that.