Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我意识到 DFA 是可数的,因为特定语言的 DFA 是所有 DFA 的子集。只是想知道如何证明接受特定语言的 DFA 的数量是无限的?
为您的语言选择任何 DFA。它必须包含其他一些循环/循环。添加与循环对应的一组新状态,并允许这组状态表示奇数次通过循环/循环(原始状态表示偶数次通过)。如有必要,添加不确定性并使用 powerset 构造将 NFA 转回 DFA。
无论哪种方式,您最终都会得到具有更多状态的相同语言的 DFA。