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

Question

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?

Answer 1

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.