Search code examples
grammarcontext-free-grammarkleene-starchomsky-normal-form

Kleene Closure in Chomsky Normal Form

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?
Solution

  • 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!