如何檢查我的線是否與NFA相符？

我製作了來自正則表達式3d數組的NFA，例如（01 *）表達式。我得到它：如何檢查我的線是否與NFA相符？

[[FROM,TO,TRANSITION]] 

    [['q0', 'q1', '0'], ['q1', 'q2', ':e:'] ,['q1', 'q4', ':e:'] , 
    ['q2', 'q3', '1'], ['q3', 'q2', ':e:'], ['q3', 'q4', ':e:']

如何編寫一個方法，可以測試滿足此自動機的字符串？例如"011111"將返回q0 q1 q2 q3 q2 q3 q2 q3 q2 q3 q2 q3 q4

來源

2017-04-16 Eywa

那麼，如果自動機是確定性的，你會知道該怎麼做嗎？ – timgeb

（如果是的話，將搜索引擎foo應用於構建DFA的算法） – timgeb

您可以使用很多現有的庫，因此您不必重新編寫該weel。我建議使用http://www.brics.dk/automaton/，這是一種適用於Java的工業強度，易於使用的自動機包。它確實是你想要的。如果您需要更多關於爲了匹配給定字符串而採取的特定轉換的更多信息，擴展Automaton類也很容易。 – Julian

您可以將自動轉換爲DFA（後檢查變得微不足道）。這種方法很有用，NFA很小，但你要測試的字符串數量非常大。
你也可以建立一個新的圖形，其中每個頂點是對（NFA的狀態，在字符串中的位置）。如果它是一個epsilon轉換，每個位置的狀態和另一個狀態之間有一個邊界。如果自動機中s->s'轉換的字符與字符串中位置爲pos的字符匹配，則還有一個優勢(s, pos) -> (s', pos + 1)。
建立圖表後，你只需要檢查一對(t, string.length())可達至少一個終端狀態t（你可以使用任何圖形遍歷算法來檢查它，比如深度優先搜索）。

來源

2017-04-16 22:26:10 kraskevich

如何檢查我的線是否與NFA相符？

回答

相關問題