1

我意识到 DFA 是可数的，因为特定语言的 DFA 是所有 DFA 的子集。只是想知道如何证明接受特定语言的 DFA 的数量是无限的？

4

1 回答 1

2

为您的语言选择任何 DFA。它必须包含其他一些循环/循环。添加与循环对应的一组新状态，并允许这组状态表示奇数次通过循环/循环（原始状态表示偶数次通过）。如有必要，添加不确定性并使用 powerset 构造将 NFA 转回 DFA。

无论哪种方式，您最终都会得到具有更多状态的相同语言的 DFA。

于 2012-02-09T03:34:28.753 回答