前端之家收集整理的这篇文章主要介绍了
正则表达式 – 将正则表达式转换为CFG，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
如何将一些常规语言转换为等效的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上>使用初始状态作为语法中的初始符号
