我是这么想的，因为上限是 2^n，并且鉴于它们都是有限机器，n 状态 NFA 和具有 2^n 或更少状态的 DFA 的交集将是有效的。
我在这里错了吗？
问问题
1062 次
2 回答
1
That is correct. As you probably already know, both DFAs and NFAs only accept regular languages. That means that they are equal in the languages they can accept. Also, the most primitive way of transforming a NFA to a DFA is with subset construction (also called powerset construction), where you simply create a state in the DFA for every combination of states in the NFA. This is called the powerset of states, which could at most be 2^n.
But, as mentioned by @SasQ that is the worst case scenario. Typically you will not end up with that many states if you use Hopcroft's algorithm or Brozowski's algorithm.
于 2011-03-09T06:49:04.367 回答
1
你是对的。2^n 是一个上限，因此生成的 DFA 的状态不能超过该限制。但这是最坏的情况。在最常见的情况下，状态比生成的 DFA 中的状态少。有时它甚至可能比原来的 NFA 还要少。
但据我所知，预测生成的 DFA 实际具有多少状态的算法还不存在。所以如果你能找到它，请告诉我；）
于 2011-03-09T06:24:05.883 回答