将正则表达式转换为CFG [英] Convert regular expression to CFG

问题描述

如何将某些常规语言转换为其等效的上下文无关语法? 是否有必要构造与该正则表达式相对应的DFA，或者有某种转换规则?

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 regular expression

01 + 10(11) ^*

如何描述与上述RE相对应的语法?

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

推荐答案

• 将A + B更改为语法

  • Change A+B to grammar

    G -> A
    G -> B
    

  • 将A *更改为

  • Change A* to

    G -> (empty)
    G -> A G
    

  • 将AB更改为

  • Change AB to

    G -> AB
    

  ，然后对A和B进行递归处理.基本情况是空语言(无生产)和单个符号.

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

  以您的情况

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

  如果语言是通过有限自动机描述的:

  If the language is described by finite automaton:

  • 将状态用作非终结符
  • 将语言用作终端符号集
  • 在原始自动机的字母a上为任何过渡p-> q添加过渡p-> aq
  • 使用初始状态作为语法中的初始符号

  这篇关于将正则表达式转换为CFG的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！