NFA 到 DFA 的转换，其语言是 L(A) 的补集
有人可以帮我解决这个问题吗？
描述一种将 NFA 转换为 DFA 的算法，其语言是 L(A) 的补集。补码应该根据 A 的字母表来考虑。给出一个关于为什么你的构造有效的非正式论证。您不需要提供正式的证明。
任何形式的指导都值得赞赏......
Can someone please help me with this question?
Describe an algorithm that converts an NFA into a DFA whose language is the complement of L(A). The complement should be taken with respect to the alphabet of A. Given an informal argument for why your construction works. You need not give a formal proof.
Any kind of guidance is appreciated...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以通过将 FA 的接受状态转换为非接受状态，并将其非接受状态转换为接受状态，将 FA 转换为其补集。简单的！
您可以通过将任何 NFA 状态视为状态的幂来将 NFA 转换为 DFA：也就是说，对于 NFA 中的每个状态，它要么是活动的，要么是非活动的。您可以将其中每个状态映射到 DFA 中的一个状态，这样您的 DFA 最多就会有 2 个代表您的 NFA 的|Q| 状态。
编辑：该算法及其证明实际上不需要 A 的详细信息，只要它是有效的有限状态自动机即可。
You can convert a FA to its complement by turning its accept states into non-accept states, and turning its non-accept states into accept states. Easy!
You can convert a NFA to a DFA by considering that any NFA state is a power of the states: that is, for each state in the NFA, it is either active or not active. You can map each of these states to a state in a DFA, so you end up with at most 2|Q| states for your DFA which represents your NFA.
Edit: this algorithm and its proof do not actually need the details of A, so long as it is a valid Finite State Automaton.