NFA 到 DFA 转换的简洁描述？
有比我聪明得多的人可以向 SO 社区简洁地描述 NFA 到 DFA 的转换算法吗？ （最好在 500 字以内。）我见过一些图表和讲座，它们只会让我以为自己曾经知道的东西变得混乱。我对从状态图生成初始 NFA 转换表非常有信心，但在那之后，我失去了 epsilon 和子集中的 DFA。
1) 在转换（增量）表中，哪一列代表新的 DFA 状态？它是生成状态的第一列吗？
2) 在下面示例的第 {2,3} 行第 0 列中，就 NFA 的状态图而言，{2,3} 意味着什么？ （抱歉，我必须用图片来思考。）我认为这将是 DFA 中的“输入 0 上的环回”？
3) 关于从表到 DFA 或识别结果 DFA 的接受状态有什么简单的“经验法则”吗？
有限自主
delta | 0 | 1 |
=======+=======+========+
{1} |{1} |{2} |
{2} |{3} |{2,3} |
{3} |{2} |{2,4} |
{2,3} |{2,3} |{2,3,4} |
{2,4} |{3,4} |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4} |{2,4} |{2,4} |
编辑：这是上表的点格式，欢呼Regexident。
digraph dfa {
rankdir = LR;
size = "8,5"
/* node [shape = doublecircle]; "1";*/
node [shape = circle];
"1" -> "1" [ label = "0" ];
"1" -> "2" [ label = "1" ];
"2" -> "3" [ label = "0" ];
"2" -> "2_3" [ label = "1" ];
"3" -> "2" [ label = "0" ];
"3" -> "2_4" [ label = "1" ];
"2_3" -> "2_3" [ label = "0" ];
"2_3" -> "2_3_4" [ label = "1" ];
"2_4" -> "2_3" [ label = "0" ];
"2_4" -> "2_3_4" [ label = "1" ];
"2_3_4" -> "2_3_4" [ label = "0" ];
"2_3_4" -> "2_3_4" [ label = "1" ];
"3_4" -> "2_4" [ label = "0" ];
"3_4" -> "2_4" [ label = "1" ];
}
此处以渲染形式显示：
注意： 该表缺少有关状态接受的任何信息，因此图表也是如此。
Can someone much brighter than I succinctly describe to the SO community the NFA to DFA conversion algorithm? (Preferably in 500 words or less.) I've seen diagrams and lectures that have only served to confuse what I thought I once knew. I'm mostly confident in generating an initial NFA transition table from a state diagram, but after that, I lose the DFA in the epsilons and subsets.
1) In a transition (delta) table, which column represents the new DFA states? Is it the first column of generated states?
2) In row {2,3}, col 0 of my example below, what does the {2,3} mean about the NFA in terms of its state diagram? (Sorry, I must think in pictures.) And I assume it will be a "loop-back on input 0" in the DFA?
3) Any simple "rules of thumb" on getting from the table to the DFA or on recognizing the accept states of the resulting DFA?
Finitely Autonomous
delta | 0 | 1 |
=======+=======+========+
{1} |{1} |{2} |
{2} |{3} |{2,3} |
{3} |{2} |{2,4} |
{2,3} |{2,3} |{2,3,4} |
{2,4} |{3,4} |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4} |{2,4} |{2,4} |
Edit: Here is the above table in dot format, cheers Regexident.
digraph dfa {
rankdir = LR;
size = "8,5"
/* node [shape = doublecircle]; "1";*/
node [shape = circle];
"1" -> "1" [ label = "0" ];
"1" -> "2" [ label = "1" ];
"2" -> "3" [ label = "0" ];
"2" -> "2_3" [ label = "1" ];
"3" -> "2" [ label = "0" ];
"3" -> "2_4" [ label = "1" ];
"2_3" -> "2_3" [ label = "0" ];
"2_3" -> "2_3_4" [ label = "1" ];
"2_4" -> "2_3" [ label = "0" ];
"2_4" -> "2_3_4" [ label = "1" ];
"2_3_4" -> "2_3_4" [ label = "0" ];
"2_3_4" -> "2_3_4" [ label = "1" ];
"3_4" -> "2_4" [ label = "0" ];
"3_4" -> "2_4" [ label = "1" ];
}
And here in rendered form:
Note: The table lacks any information regarding state acceptance, hence so does the graph.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
当您从 NFA 构建 DFA 时，您基本上会找到 NFA 在某个时间可能处于的状态集（例如模拟 NFA）。首先从起始状态开始，然后找到通过 epsilon 转换可以到达的所有状态。这组状态形成了生成的 DFA 的起始状态。然后，您可以跟踪此状态集的传出转换。这些可能会导致另一个 NFA 状态，因为您会再次通过 epsilon 输入找到可到达的状态，并且您将获得另一组 NFA 状态，这将是一个新的 DFA 状态。您执行此过程直至完成。
关键是，生成的 DFA 状态将成为旧 NFA 状态的集合，它们是兼容的（关于 epsilon 转换）。这些集合也可能重叠，这没有错误。现在我可以回答您的问题：
1）第一列代表新的 DFA 状态。它显示形成给定 DFA 状态的 NFA 状态集。
2）你的假设是正确的，这意味着在0输入上环回状态{2,3}。
3）可以根据该表轻松构建DFA表，只需用字母命名您的州即可。任何包含至少一个 NFA 接受状态的 DFA 状态也将成为 DFA 中的接受状态。
我希望我说得足够清楚。
When you construct a DFA from an NFA you basically find those sets of states that the NFA can be in a time (like simulating the NFA). First you begin with the start state and then find all states that can be reached through epsilon transitions. This set of states form the start state of the resulting DFA. Then you follow the outgoing transitions from this state set. Those may lead to another NFA state, for that you find the states reachable through epsilon inputs again, and you will get another set of NFA states that will be a new DFA state. You do this process until you have finished.
The point is, that the resulting DFA states will become sets of the old NFA states, that are compatible (regarding to epsilon transitions). These sets may also overlap, that is no error. And now I can answer your questions:
1) The first column represents the new DFA states. It shows the NFA state sets that form the given DFA state.
2) Your assumption is correct, it means loopback to state {2,3} on 0 input.
3) The DFA table can be easily constructed from this table, just name your states with letters. Any DFA states that contain at least one NFA accept state will become accept states in the DFA, too.
I hope I was clear enough.
核心思想可能是理解DFA是一种叠加在NFA之上的机器。虽然 NFA 在节点数量或其与问题的关系方面更简单，但它的规则相当微妙且复杂（它进入正确状态，无论哪种状态）。 dfa 就其包含的节点而言要复杂得多，但规则非常简单，因为任何给定输入都只有一个输出状态。
这种转变相当简单。 DFA 中的每个状态都是 NFA 中状态的子集。 DFA的起始状态是仅包含NFA的起始状态的集合，DFA的接受状态是其所有以NFA的接受状态为元素的状态。
DFA 中的过渡是唯一棘手的部分。 NFA 是非确定性的，因为给定输入的输出状态是一组状态，但 DFA 将相应的 NFA 状态集作为其自己的状态，表示自动机可以实现哪些 NFA 状态 处于。因此，任何给定输入的任何 DFA 状态的输出状态都是该 DFA 状态的所有 NFA 状态的输出状态的并。
就实际实现而言，DFA 的状态人口本质上是 NFA 状态的幂集。 IE，n 个 NFA 状态为 2^(n)。在实践中，它通常要小得多，但没有通用的方法来预测它的大小，因此一些实用的 NFA 到 DFA 实现会在到达 DFA 状态时动态生成它们并缓存它们。一旦创建了一定数量的状态，最近最少使用的状态就会被丢弃，从而限制了缓存的大小。
The core idea Is probably to understand that the DFA is a sort of machine that is superimposed over the NFA. While the NFA is simpler in terms of the number of nodes, or its relationship with the problem, it's rules are quite subtle and compled (it goes into the right state, whichever that might be). The dfa is much more complex in terms of the nodes it contains, but has really simple rules, since there is exactly one output state for any given input.
The transformation is pretty straitforward. each state in the DFA is a subset of the states in the NFA. The start state of the DFA is the set containing only the start state of the NFA, and the accept state for the DFA is all of its states which have the accept state of the NFA as elements.
The transitions in the DFA are the only tricky party. an NFA is non-deterministic because its output states for a given input is a set of states, but the DFA has sets of the corresponding NFA states as its own states, representing which of the NFA states the automaton could be in. So the output state of any DFA state for any given input is the union of output states of all of the NFA states of that DFA state.
In terms of actual implementations, the DFA has a state population that is essentially the powerset of the NFA's states. IE, 2^(n) for n NFA states. In practice it's usually much smaller, but there's no general way to predict it's size, so some practical NFA to DFA implementations generate the DFA states dynamically as they are reached and cache them. Once a certain number of states are created, the least recently used is discarded, limiting the size of the cache.
假设输入 NFA 为 (S, Q, q0, T, F)，其中 S 是输入符号集合，Q 是状态集合，q0 是起始状态，T 是转换集合，F 是集合接受国家。每个转换都是一个三元组 (q, s, r)，其中 q 和 r 是状态，s 是长度为 0 或 1 的字符串。
对于任何有限字符串 s，令 D(s) 为可以到达的所有状态的集合从 q0 开始，遵循一条转换路径，其标签连接在一起形成 s。
该算法需要做的是构造一个确定性自动机，其状态是 Q 的子集，这样对于任何字符串 s，DFA 将最终处于状态 D(s)。
如果是这种情况，则任何包含 NFA 接受状态的 DFA 状态都应该是 DFA 接受状态。
考虑空字符串 epsilon； D(“”) 将是 q0 的 epsilon 闭包，即从 q0 可以到达的所有状态，仅遵循用空字符串标记的转换。我们称之为 Set Q0。 （在您的示例中，D(“”)={1}。）现在我们“探索”该状态，这意味着：对于每个输入符号 a，您可以计算出该符号从该状态转移到何处。这会导致您发现更多需要包含在 DFA 中的状态。 （在您的示例中 S={0,1}，因此这些状态将为 D(“0”)={1} 和 D(“1”)={2}。但 D(“0”) 与D{“”);所以这并不新鲜。因此，现在唯一已发现但尚未探索的状态是 D(“1”)。）并且继续探索状态，直到没有更多已发现但尚未探索的状态。
Suppose the input NFA is (S, Q, q0, T, F) where S is the set of input symbols, Q is the set of states, q0 is the start state, T is a set of transitions, and F is the set of accepting states. Each transition is a triple (q, s, r) where q and r are states and s is a string of length 0 or 1.
For any finite string s, let D(s) be the set of all states that can be reached from q0 following a path of transitions whose labels catenate together to make s.
What the algorithm needs to do is to construct a deterministic automaton whose states are subsets of Q and such that for any string s, the DFA will end up in state D(s).
If that’s the case, then any DFA state that contains an accepting state of the NFA should be an accepting state of the DFA.
Consider the empty string, epsilon; D( “” ) will be the epsilon-closure of q0, i.e. all the states you can reach from q0, following only transitions labeled with the empty string. Let’s call that Set Q0. (In your example D(“”)={1}.) Now we “explore” that state, which means that: for each input symbol a, you figure out where the transition for that symbol, out of the state should go. That results in you discovering a bunch more states that need to be in the DFA. (In your example S={0,1}, so these states will be D(“0“)={1} and D(“1”)={2}. But D(“0”) is the same as D{“”); so it’s not new. So the only state now that has been discovered, but not explored is D(“1”).) And just keep exploring states until there are no more states left that have been discovered but haven’t been explored.