Convert regular expression to CFG

Question

How can I convert some regular language to its equivalent Context Free Grammar? Whether the DFA corresponding to that regular expression is required to be constructed or is there some rule for the above conversion?

For example, considering the following regular expression

01+10(11)^*

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

Answer 1

I guess you mean convert it to a formal grammar with rules of the form V->w, where V is a nonterminal and w is a string of terminals/nonterminals. To start, you can simply say (mixing CFG and regex syntax):

S -> 01+10(11)*

Where S is the start symbol. Now let's break it up a bit (and add whitespace for clarity):

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

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

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

Finally, we'll convert + 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?, simply split it into a rule producing empty and a rule producing x .

Answer 2

• Change A+B to grammar

  G -> A
  G -> B
  

• Change A* to

  G -> (empty)
  G -> A G
  

• Change AB to

  G -> AB
  

and proceed recursively on A and B. Base cases are empty language (no productions) and a single symbol.

In your case

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

If the language is described by finite automaton:

• use states as nonterminal symbols
• use language as set of terminal symbols
• add a transition p -> aq for any transition p -> q on letter a in the original automaton
• use initial state as initial symbol in the grammar