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