NFA到DFA的轉換，其語言爲L的（A）補

Question

有人可以幫我這個問題？

描述，一個NFA轉換成DFA其語言是L（A）的補體的算法。應該對A的字母表進行補充。給出關於你的建築工作原因的非正式論點。您無需提供正式的證明。

任何一種指導的理解......

Answer 1

您可以通過轉動它的接受狀態到非接受狀態，並打開其非接受的狀態到接受狀態的FA轉換成它的補充。簡單！也就是說，在NFA的每個狀態下，無論是主動還是未激活：

您可以通過考慮任何NFA狀態是狀態的功率NFA轉換爲DFA。每個狀態可以映射到在DFA的狀態，所以你最終至多2 ^{| Q |您DFA}狀態，它代表了NFA。

編輯：這種算法及其證明實際上並不需要的細節，只要它是一個有效的有限狀態自動機。