0

有人可以帮我解决这个问题吗？

描述一种将 NFA 转换为语言是 L(A) 补码的 DFA 的算法。补码应针对 A 的字母表。给出一个非正式的论据来说明您的构造为何有效。您无需提供正式证明。

任何形式的指导表示赞赏...

4

1 回答 1

0

您可以通过将其接受状态转换为非接受状态并将其非接受状态转换为接受状态来将 FA 转换为其补码。简单的！

您可以通过考虑任何 NFA 状态是状态的幂来将 NFA 转换为 DFA：也就是说，对于 NFA 中的每个状态，它要么是活动的，要么是不活动的。您可以将这些状态中的每一个映射到 DFA 中的状态，因此您最终最多有 2 个|Q| 代表您的 NFA 的 DFA 的状态。

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

于 2011-04-18T07:11:23.793 回答