我是这么想的，因为上限是 2^n，并且考虑到它们都是有限机，n 状态 NFA 和具有 2^n 或更少状态的 DFA 的交集将是有效。
我错了吗？
最佳答案
你是对的。 2^n 是一个上限，因此生成的 DFA 的状态不能超过该限制。但这是最坏的情况。在大多数常见情况下，状态比生成的 DFA 中的状态少。有时它甚至可能比原始 NFA 中的还要少。
但据我所知，预测 DFA 实际具有多少状态的算法尚不存在。所以如果你找到它，请告诉我 ;)
关于deterministic - 如果一种语言 (L) 被 n 状态 NFA 识别，它是否也能被状态不超过 2^n 的 DFA 识别？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3941552/