# How to convert CFG with Kleene Star, Kleene Plus, and Question Mark to Chomsky Normal Form?

I am fairly new to formal language theory but understand how to convert simple CFGs into both Chomsky normal form and Greibach normal form. However, I have not seen any examples of how to do that when you add the Kleene Star *, Kleene Plus +, and question mark ? to that grammar, commonly seen in regular expressions.

How do you do convert CFG's with Kleene Star/Plus, and question mark, to CNF?

Say the grammar is like this:

S -> A+
A -> BX?
B -> a+ // letters
X -> ! // exclamation


How do you convert this to Chomsky Normal Form, given that it uses *, +, and ?? In particular, I am wondering what the general pattern is to convert the Kleene Star/Plus and question mark to CNF, not necessarily how to do it in this example, but whichever is easiest to demonstrate.

Is it something like this?

// first step
S -> A+
A -> BX?
B -> a+
X -> !

// replace + with *
S -> AA*
A -> BX | B
B -> aa*
X -> !

// replace * with new rules and ɛ
S -> AI
I -> A | ɛ
A -> BX | B
B -> aJ
J -> a | ɛ
X -> !

// replace X -> aY with X -> ZY and Z -> a
S -> AI
I -> A | E
A -> BX | B
B -> KJ
J -> K | E
X -> !
K -> a
E -> ɛ


I am just guessing here, not sure how it is typically done. Also, from the few resources I have found, it sounds like you are supposed to also remove the epsilon rules somehow. There doesn't seem to be many thorough online resources demonstrating this though, any book recommendations?

• Pretty close. A hint: to eliminate a Kleene star you need a recursive production (try to figure out why). The Wikipedia article you link to is quite instructive about the removal of epsilon productions, and there are many other sources online. Fight harder to understand them as they come, it's a good exercise. Feel free to answer your own question, after you get it right. – André Souza Lemos Jun 7 '15 at 19:07
• You simply replace Kleele star and plus, and question mark by standard CF rules, and then you apply the standard Chomsky Normal Form (CNF) construction. However I am wondering what is the point of the question. CNF is used primarily for theoretical proofs, while Kleene star/plus and question mark are pragmatic extensions. They should not have to meet. The same is true for Greibach Normal Form, though GNF was originally motivated by pragmatic issues (lexicalisation of CF hrammars). – babou Jun 7 '15 at 19:14

How do you do convert CFG's with Kleene Star/Plus, and question mark, to CNF?

I propose a two-step solution:

1. Convert your extra-notation-CFG to a normal CFG
2. Convert the normal CFG to CNF, e.g. as described on Wikipedia.

Do perform step 1, removing the extra notation, apply these rules:

1. Whenever $A^+$ occurs in a production rule, replace it with $AA^*$.
2. Whenever $A^*$ occurs in a production rule, replace it with a new non-terminal $B$ and add rules $B \rightarrow \varepsilon$ and $B \rightarrow AB$.
3. Whenever $A?$ occurs in a production rule, replace it with a new non-terminal $B$ and add rules $B \rightarrow \varepsilon$ and $B \rightarrow A$.

It should be relatively straightforward to see that the transformed versions of +,*,? repeat the argument k times, where k is in $\{1, \ldots\}$, $\{0, \ldots\}$ and $\{0, 1\}$, respectively; i.e. the rewritten version has the same meaning (language) as the input.

To perform step 2, read the Wikipedia article; it is reasonably straightforward (if a bit tedious) to translate this into an algorithm.