2
什么是将任何给定的正则表达式（RE）转换为左（或右）线性语法的标准算法？将正则表达式转换为线性语法的算法
我知道我能做到这一点是这样的（写从RE线性语法）：
RegEx -> NFA -> DFA -> Right Linear grammar。
对于直接的方法，我可以处理简单的正则表达式，如(0 + 10)*并创建线性语法。
但是，当存在嵌套的kleene恒星时，如果没有任何明确定义的方法，则很难生成线性的CFG。
我看到类似问题here和here的一些答案。但是它们不提供通用算法，也不会将正则表达式转换为线性语法。
特别是，如何使用某种算法将此：(((01+10)*00)*11)*直接转换为线性语法？
任何帮助表示赞赏。
编辑
没有更多的搜索。并得到了这个。
Constructing an Equivalent Regular Grammar from a Regular Expression
http://www-cs.ccny.cuny.edu/~vmitsou/304spring10/slides/lineargrammars.pptx从http://www-cs.ccny.cuny.edu/ 〜vmitsou/304spring10/sched.html似乎回答你的问题。 – nhahtdh 2013-04-11 03:34:03
嗨你的建议是正确的[我的答案在这里]（http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars?answertab=votes#tab-top）我犯了一些愚蠢的错误。但在我批准你编辑之前，其他用户拒绝。现在我纠正了我的答案。我有请求请再次检查，以便一个新人可以得到正确的帮助。我可以在晚上帮你解决这个问题...谢谢！ – 2013-04-11 05:00:09
总之，我可以回答你*标准算法*为RE到线性语法（LG）。算法从RE到DFA首先发生在两个步骤，然后算法DFA到LG（**因此搜索两个算法**）。虽然我们有规则语言的正则表达式的幸运因为正则表达式和语法使用相同的目的，但对于其他常规语言我们没有任何正则表达式类型机制来表达语言。对于RL我们有RE和Grammar。 – 2013-04-11 05:14:08