NFA到DFA的转换，其语言为L的（A）补

Question

有人可以帮我这个问题？

描述，一个NFA转换成DFA其语言是L（A）的补体的算法。应该对A的字母表进行补充。给出关于你的建筑工作原因的非正式论点。您无需提供正式的证明。

任何一种指导的理解......

Answer 1

您可以通过转动它的接受状态到非接受状态，并打开其非接受的状态到接受状态的FA转换成它的补充。简单！也就是说，在NFA的每个状态下，无论是主动还是未激活：

您可以通过考虑任何NFA状态是状态的功率NFA转换为DFA。每个状态可以映射到在DFA的状态，所以你最终至多2 ^{| Q |您DFA}状态，它代表了NFA。

编辑：这种算法及其证明实际上并不需要的细节，只要它是一个有效的有限状态自动机。