Kleene Closure in Chomsky Normal Form

Question

Let n be any terminal.

Consider the following, presumably correct, representation of the kleene star over n:

N → n N | ε

(where ε is the empty terminal.)

Wikipedia says:

Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form.

I cannot see how the above grammar could be transformed to CNF.

• Is the grammar not context-free?
• Is there in fact a way to represent it in CNF?

Answer 1

Fortunately, this can be written in CNF. Here is one such grammar:

S → ε | n | NA

N → n

A → n | NA

Therefore, the language is context-free.

Hope this helps!