如何將NFA轉換爲正則表達式

我知道將正則表達式轉換爲NFA是一種算法。如何將NFA轉換爲正則表達式

但我想知道是否有算法將NFA轉換爲正則表達式。如果有，它是什麼？

如果沒有，我也想知道是否所有的NFA都可以轉換爲正則表達式。是否存在無法表示正則表達式的NFA？

謝謝！：d

2012-02-09 formatjam

正則表達式可以表達*任何*正則語言，所以有應該對每個可能的NFA至少存在一個正則表達式。但是，我不知道從頭到尾從NFA走向正則表達式的算法。 – 2012-02-09 05:20:04

此外，你的時間確實是令人毛骨悚然 - 我的朋友今天在課堂上問了同樣的問題。我不記得答案然後:( – 2012-02-09 05:24:37

在這裏看到你的問題的各種答案：http://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-表達式 – Masterfool 2014-11-15 04:15:29

下面是其中每個過渡遞增與正則表達式替換的算法，直到只有一個初始和最終狀態：https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf [PDF]

2012-02-09 05:43:05 buzypi

這是正確的，但它是行不通的，如果你有很多的節點，它對一個簡單的節點和少數節點有好處，有沒有其他的建議？ – 2013-10-22 20:10:18

鏈接已經死了我發現這個鏈接想：https：/ /courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf – 2015-05-30 16:48:13

回答