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

To begin conversion to Chomsky normal form (using Definition (1) provided by the Wikipedia page), you need to find an equivalent essentially noncontracting grammar. A grammar G with start symbol S is essentially noncontracting iff

1. S is not a recursive variable
2. G has no ε-rules other than S -> ε if ε ∈ L(G)

Calling your grammar G, an equivalent grammar G' with a non-recursive start symbol is:

G' : S -> A
     A -> aAb | bAa | ε

Clearly, the set of nullable variables of G' is {S,A}, since A -> ε is a production in G' and S -> A is a chain rule. I assume that you have been given an algorithm for removing ε-rules from a grammar. That algorithm should produce a grammar similar to:

G'' : S -> A | ε
      A -> aAb | bAa | ab | ba

The grammar G'' is essentially noncontracting; you can now apply the remaining algorithms to the grammar to find an equivalent grammar in Chomsky normal form.

Answer 2

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.