NFA轉化爲DFA =確定性？

Question

我在決定論和非決定論的意義上掙扎了一下。當涉及到自動機時，我得到了不同，但我似乎無法找到以下答案：NFA轉換爲DFA轉換是否具有確定性？

如果可以爲同一常規語言構建多個DFA，那麼這是否意味着NFA轉換爲DFA的結果不是唯一的？因此一個非確定性算法？

我很高興你可以提供任何信息。

在此先感謝！

Answer 1

在這裏玩有兩個不同的概念。首先，你是正確的，可以有許多不同的DFA等價於相同的NFA，就像可以有許多相互等價的NFA一樣。

獨立地，有幾種將NFA轉換爲DFA的算法。在大多數正式語言入門課程中教授的標準算法是子集構建（也稱爲powerset構建）。該算法是確定性的 - 將NFA轉換爲DFA需要遵循特定的步驟順序，因此，只要您使用同一個NFA，就會始終返回相同的DFA。您可以想象，將NFA轉換爲DFA的算法可能會產生許多不同的DFA中的一種作爲輸出，但據我所知，沒有任何這種着名的算法。

希望這會有所幫助！