NFA 到 DFA 的问题
首先，这不是一个要求将 NFA 转换为 DFA 的算法的问题。
众所周知（并已证明），NFA 的等效 DFA 最多具有 2n 个状态，尽管大多数时候它的状态数量或多或少与 NFA 相同。
我如何预测 NFA 等效 DFA 将具有的状态数量的估计值？哪种特定类型的 NFA 需要等效的 DFA 具有 2n 个状态？
我问这个问题的原因是能够“发明”一些 NFA，在不考虑最小化的情况下，它们肯定会产生 2n - 1 个状态加上“死状态”。
First, this is not a question asking for the algorithm to convert a NFA to DFA.
It's known (and proved) that the equivalent DFA of a NFA has at most 2n states, even though most of the times it will have more or less the same number of states as the NFA.
How may I predict an estimate for the number of states the NFA-equivalent DFA will have? Which particular type of NFA will require an equivalent DFA to have 2n states?
My reason for asking this is to be able to "invent" some NFAs that will certainly produce, without considering minimization, 2n - 1 states plus the "dead state".
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
由于非确定性，状态数量呈爆炸式增长，这是你问题的关键。
如果你采用一个 NFA，其中每个转换都是唯一确定的，即确定性 NFA，那么它只不过是一个普通的 DFA。然而，一旦达到可能进行两次转换的状态，它就与 DFA 不同。
考虑转换算法，并看看如果某个状态有两个或多个具有相同标签的转换会发生什么。这就是您需要与状态集相对应的新状态的地方。
因此，问题归结为找出这些超集状态中有多少实际上是可以到达的。当然，您可以为此发明一种奇特的算法，但要获得正确的数字，只需运行正常的转换算法并删除无法到达的状态即可。
对于具有 n 个状态的 NFA（其等效 DFA 有 2^n 个状态），请考虑利用非确定性。第一个想法是将所有转换标记为相同，但是效果不太好。相反，请记住，您需要能够以某种方式到达状态的所有子集，每个子集都有一些标签。
如果不计算起始状态，则可以执行以下构造：创建 n 个节点，并为 2^n 中的每个集合创建一个唯一标签，并在 NFA 中向该集合的每个节点添加带有此标签的转换。这为您提供了具有 n+1 个状态的 NFA（1 是起始状态），其中 DFA 需要 2^n +1 个状态。当然，一旦您想在最小化后拥有 2^n 个 DFA 状态，事情就会变得更加棘手。
The number of states explodes due to non-determinism, which is the key to your question.
If you take an NFA, where each transition is uniquely determined, i.e. a deterministic NFA, then it is nothing but a normal DFA. However, once you have a state where two transitions are possible it differs from the DFA.
Consider the conversion algorithm and look at what happens if you have two or more transitions with the same label for a state. This is where you need those new states that correspond to sets of states.
So the question comes down to finding out how many of these superset states are actually reachable. Of course you could invent a fancy algorithm for that, but to get the correct number, simply run the normal conversion algorithm and remove unreachable states.
As for an NFA with n states for which the equivalent DFA has 2^n states think about exploiting non-determinism. The first idea would be to label all transitions the same, however, that doesn't work out too well. Instead remember that you need to be able to somehow reach all subsets of states with some label each.
If you do not count the starting state, then you can do the following construction: create n nodes and for each set out of 2^n create a unique label and in the NFA add a transition with this label to each node of that set. This gives you a NFA with n+1 states (1 being the starting state), where the DFA requires 2^n +1 states. Of course, it gets trickier, once you want to have 2^n DFA states after minimization.
好的，首先假设 n ->名词
现在，对于从一个状态到 x 个其他状态的每个非确定性转换，将您的估计值乘以 x。这可能不准确，因为您可能会重复计算。但它应该给你一个上限。
然而，唯一可靠的方法是构建相应的 DFA，然后对状态进行计数（我认为）。
最后，您可能可以简化一些 DFA（以及 NFA），但这是一个全新的故事......
Ok, start with assumption that n -> n.
Now, for every non-deterministic transition where from one state you can end up in x other states, multiply your estimate by x. This may not be precise, as you might double-count. But it should give you an upper bound.
However, the only sure way it to build a corresponding DFA and then count the states (I think).
Finally, you can probably simplify some of the DFAs (and NFAs for that matter), but this is a whole new story ...
作为 N 的函数，起始状态为 S，最终状态为 N，这个 NFA
A(N)：很明显，它接受
[ab]*中的所有字符串> 倒数第 N 个字母是a。A(N)的确定必须有效地记住前面的 N-1 个字母（您需要知道该窗口中所有a的位置，以便当字符串意外结束，你可以说是否有一个aN个字母之前）。我不确定这是否正好达到您想要的状态数，但至少在 2 倍之内 -
{0,...,N}的所有子集都是可能的，但您也总是在S中。这应该是2^(N+1)状态，但是A(N)有N+2状态。Take as a function of N, with start state S and final state N, this NFA
A(N):It should be obvious that this accepts all strings in
[ab]*whose Nth-from-last letter isa.The determinization of
A(N)has to remember the previous N-1 letters, effectively (you need to know all the positions in that window that werea, so that when the string unexpectedly ends, you can say whether there was anaN letters ago).I'm not sure if this hits exactly the number of states you wanted, but it's at least within a factor of 2 - all subsets of
{0,...,N}are possible, but you're also always inS. This should be2^(N+1)states, butA(N)hadN+2states.进一步扩展乔纳森·格雷尔的出色答案。
向
A(N)的每个状态0, 1, ..., N添加一个标记为c的自循环，即添加以下内容过渡：<代码> 0 c-> 0
<代码>1 c-> 1
<代码>...
NC-> N然后假设
c从不触发，DFA 包含与 Jonathan 的 DFA 相同的2^(N+1)状态。然而，每当从状态{S,j,k,...,z} <> 观察到我们到达状态c时， {S}{j,k,...,z}。因此，除了空集之外，{S,0,...,N}的所有子集都是可能的，并且 DFA 具有2^(N+2)-1状态，而A(N)有N+2个状态。To further expand on the excellent answer of Jonathan Graehl.
Add to each state
0, 1, ..., NofA(N)a selfloop labeledc, i.e., you add the following transitions:0 c-> 01 c-> 1...N c-> NThen assuming
cnever fires, the DFA contains the same2^(N+1)states of Jonathan's DFA. However, whenevercis observed from a state{S,j,k,...,z} <> {S}we reach state{j,k,...,z}. Hence all subsets of{S,0,...,N}are possible except the empty set and the DFA has2^(N+2)-1states whileA(N)hasN+2states.