开发者

Convert regular expression to CFG

How can I convert some regular language to its equivalent Context Free Grammar? Is it necessary to construct the DFA corresponding to that regular expression or is there some rule for such a conversion?

For example, consider the following regula开发者_StackOverflowr expression

01+10(11)*

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


  • 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 -> 11B

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


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 .


Actually, different CFG grammars can produce the same language. So given a regular expression (regular language), its mapping back a CFG is not unique.

Definitely, you can construct a CFG that result in a given regular expression. The above answers shown some ways to achieve this.

Hope this gives you a high level idea.


For the example, the following grammar is equivalent:

S -> 01|10A
A -> 11A|empty
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜