Convert Regular Expression to CFG

Question

How can I convert some ordinary language into its equivalent free context grammar? Do I need to build a DFA that matches this regular expression, or is there some kind of rule for such a conversion?

For example, consider the following regular expression

01 + 10 (11) ^*

How can I describe a grammar corresponding to the above RE?

Answer 1

• Change A + B to Grammar

  G -> A G -> B 

• Change A * to

   G -> (empty) G -> AG 

• Change AB to

   G -> AB 

and go recursively to A and B. The basic cases are an empty language (without productions) and one character.

In your case

  A -> 01 A -> 10B B -> (empty) B -> 11B 

If the language is described by a state machine:

• use states as nonterminal characters
• use language as a set of terminal characters
• add the transition p → aq for any transition p → q to the letter a in the original automaton
• use the source state as the source character in the grammar

Answer 2

I assume that you mean converting it to a formal grammar with rules of the form V-> w, where V is a non-terminal and w is a string of terminals / non-terminals. To get started, you can simply say (mixing CFG and regex syntax):

 S -> 01+10(11)* 

Where S is the symbol of the beginning. Now break it a bit (and add a space for clarity):

 S -> 0 A 1 0 B A -> 1+ B -> (11)* 

The key is to convert * es and + es to recursion. First, we convert the Kleene star to a plus by inserting an intermediate rule that accepts an empty string:

 S -> 0 A 1 0 B A -> 1+ B -> (empty) B -> C C -> (11)+ 

Finally, we convert the + notation to recursion:

 S -> 0 A 1 0 B A -> 1 A -> A 1 B -> (empty) B -> C C -> 11 C -> C 11 

To handle x? , just divide it into a rule that creates an empty one, and a rule that creates an x.

Answer 3

In fact, different CFG grammars can create the same language. Therefore, given the regular expression (regular language), its mapping back to CFG is not unique.

You can definitely build CFGs that result in a given regular expression. The above answers showed some ways to achieve this.

Hope this gives you a high level idea.