computer-science - 有哪些方法可以找到接受给定 NFA 接受的语言的补充的非确定性有限自动机 (NFA)？

Question

我知道找到一个接受给定 NFA 接受的语言的补充的 NFA 的唯一方法是将 NFA 转换为等效的 DFA，然后将非最终状态作为最终状态，将最终状态作为非最终状态。有没有其他方法可以达到同样的效果？

Answer 1

基本上，给定一个 NFA A，它可以转换为等价物（在接受相同语言的意义上） DFA B，反过来可以C通过使每个终端状态为非终端来修改它，反之亦然，以便接受接受的语言A。

Answer 2

我知道的唯一方法是您的解决方案。

我觉得必须有一种方法来证明不存在其他解决方案。但我现在无法建立证据。