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