Java中的NFA模擬

2011-11-29 104 views 7 likes

我已經被賦予了模擬Java中的NFA的任務。現在我必須模擬NFA的以下正則表達式是Java中的NFA模擬

ab*((b|d)|c*)

我想我有太多的電子符號。我只是想知道下面的圖片是否正確。

NFA

2011-11-29 unleashed

節點10,11,12和13可能會被壓縮成兩個節點？ –

這就是我最初的想法，但演講者希望這種風格能夠重複使用並使用湯普森建構來創建NFA。我只是懷疑2到3 e的過渡，3到4 e的過渡和4到5或4到7 e的過渡。 – unleashed

那麼，2-3可以減少，在'b *'的情況下導致沒有'b's，你會有一個從'1-2'轉換的'e'。除此之外，我認爲其餘部分似乎是合適的。最終的結果是一樣的，只有一個節點。 –

回答

你NFA圖形是正確的。它將匹配正則表達式ab*((b|d)|c*)而沒有別的。然而，它可能更簡單，例如像這樣：

enter image description here

2011-11-30 07:55:05

我不認爲這是完全正確的，分支部分'（（b | d）| c *）'是兩個分支，而不是三個，它是（b | d）或c *節點將它表示爲一個完全獨立的路徑，然後分支到'b'或'd'中是否更準確？ –

我敢肯定，上面的一個不使用湯普森建設。它比較短，但我的演講者給了我一種如何去做的風格。 – unleashed

@unleashed我會說湯普森是一種創建NFA的算法（一種程序），而不是一種NFA。你可以看到我的NFA是由湯普森創建的，然後進行了優化。（bw：問題是你的NFA是否等同於你的正則表達式，Thomspon沒有:-)） –

相關問題