有沒有一種有效的算法來決定一個NFA接受的語言是否是另一個接受的語言的超集？

給定兩個非確定性有限自動機M1和M2，是否有一個有效的算法來確定M1接受的語言是否爲M2接受的語言的一個超集？有沒有一種有效的算法來決定一個NFA接受的語言是否是另一個接受的語言的超集？

2012-02-25 Daniel Trebbien

不除非P = NP。如果你有這樣一個算法，你可以平凡地決定兩個NFA是否是同構的（只是檢查A是B的超集而B是A的超集），這是一個known NP-hard problem。欲瞭解更多詳情，read this paper。它有一個令人沮喪的複雜結果表。

來源

2012-02-26 03:15:25 Mikola

我想知道，你是否知道從另一個NP完全問題到NFA同構的減少？ – hugomg 2012-02-26 03:34:35

@missigno：我在一篇論文中增加了一個鏈接，更加仔細地解釋了減少的情況。 – Mikola 2012-02-26 04:02:57

米科拉，你的回答是正確的，但你的措辭是錯誤的：同形意味着「形狀相同」，兩個自動機是同構的，如果他們的狀態之間有1-1映射，比如bla bla。這與這裏不相關，兩個自動機可以接受相同的語言而不是同構的。（它增加了混淆，檢查圖同構也是NP-Hard）如果您將答案編輯爲「兩個NFA是否接受相同的語言」而不是「兩個NFA是否同構」，所有都會沒事的。 – 2012-02-26 11:27:25

有沒有一種有效的算法來決定一個NFA接受的語言是否是另一個接受的語言的超集？

回答

相關問題