正则表达式 – 将正则表达式转换为CFG

发布时间：2020-12-14 06:24:53 所属栏目：百科来源：网络整理

导读：如何将一些常规语言转换为等效的Context Free Grammar？是否有必要构造与该正则表达式相对应的DFA,或者是否存在某种转换规则？例如,请考虑以下正则表达式 01+10(11) * 如何描述与上述RE相对应的语法？将A B改为语法 G - AG - B 将A *改为 G - (empty)G -

如何将一些常规语言转换为等效的Context Free Grammar？
是否有必要构造与该正则表达式相对应的DFA,或者是否存在某种转换规则？

例如,请考虑以下正则表达式

01+10(11)^*

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

>将A B改为语法

G -> A
G -> B

>将A *改为

G -> (empty)
G -> A G

>将AB改为

G -> AB

并且在A和B上递归地进行.基本情况是空语言(没有产生)和单个符号.

在你的情况下

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

如果语言由有限自动机描述：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!