NFA转DFA问题

Question

首先，这不是一个关于如何将NFA转换为DFA算法的问题。

已知（并且已证明）， NFA 的等价 DFA 最多有 2ⁿ 个状态，尽管大多数情况下它将具有与 NFA 几乎相同数量的状态。

我如何预测 NFA 等价的 DFA 将具有的状态数量的估计？哪种特定类型的 NFA 需要一个等价的 DFA 具有 2ⁿ 个状态？

我之所以提出这个问题是为了能够“发明”一些 NFA，这些 NFA 将肯定产生 2ⁿ -1 个状态加上“死状态”，而不考虑最小化。

- nunos

---

我5年前上过这门课。你能举一个非确定有限状态自动机的例子吗？ - Hamish Grubijan

NFA是一种状态机，其中对于给定的状态和给定的输入标记，存在多种转换可能性。因此，NFA可以是这样一个状态机：使用'a'可以从状态1到达状态2或状态3，或者具有自环或epsilon转换（不需要输入标记的转换）。 - danben

你是不是想说如何通过编程预测DFA会有多少个状态，而无需实际生成DFA？在我看来，任何用于预测状态数量的算法本质上都等同于生成自动机的算法，因此预测状态数量并不能节省工作量。不过如果有人能告诉我相反的情况，我会非常高兴。我认为具有最大非确定性分支的NFA会产生最复杂的DFA。 - Nate C-K

Answer 1

由于“非确定性”而导致状态数量激增，这才是你问题的关键。如果你拿一个每个转换都唯一确定的NFA，即确定性NFA，则与普通DFA没有区别。然而，一旦出现两个转换都可能的状态，它就与DFA不同了。看看转换算法，如果一个状态有两个或更多标签相同的转换会发生什么。这就是需要那些对应于状态集合的新状态的地方。所以问题就在于找出有多少这样的超集状态实际上是可达的。当然，你可以发明一个花哨的算法来解决这个问题，但为了得到正确的数字，只需运行常规的转换算法并删除不可达状态。至于具有n个状态的NFA，其等效DFA具有2^n个状态，考虑利用非确定性。第一个想法是将所有转换标记相同，但这样效果不太好。相反，记住你需要能够以某个标签到达所有子状态集。如果不计算起始状态，那么可以进行以下构造：创建n个节点，并为2^n中的每个集合创建一个唯一标签，在NFA中为该集合的每个节点添加一个具有此标签的转换。这给你一个具有n +1个状态（1是起始状态）的NFA，而DFA需要2^n +1个状态。当然，一旦你想要最小化后拥有2^n个DFA状态，情况就会变得更加棘手。

- Frank

---

@Frank -- 有下限证明吗（链接？）-- 例如，是否存在一组NFA族，其中接受相同语言的最小DFA随着NFA中状态数量的增加呈指数增长？ - shaunc

Answer 2

首先，我们假设n -> n。

对于每个非确定性转换，如果从一个状态可以到达x个其他状态，就将估计乘以x。由于可能会重复计算，因此这可能不是精确的，但应该可以给出一个上限。

然而，唯一确定的方法是构建相应的DFA，然后计算状态数（我认为）。

最后，您可能可以简化一些DFA（以及NFA），但这是另一个故事……

- Hamish Grubijan

---

我并不完全认为这是有用的。考虑一个具有状态1、2和3的NFA，其中在令牌'a'上从1到2和1到3转换。2和3是最终状态。由于合并，结果DFA具有比NFA更少的状态和转换。因此，乘法似乎是朝着错误的方向迈出的一步。 - danben

我给出了一个粗略的上限，因为你可以构想出最坏情况下会发生的NFA。除此之外，你需要实际将NFA转换成DFA，并计算状态数。这有点像是说 - 我有一个程序有10个if语句，没有递归或for循环 - 有多少代码路径？嗯，可能只有一条代码路径，但你必须面对最坏情况，并且不能在没有仔细检查、或编译成汇编并计算跳转指令等情况下确定有多少种可能性。 - Hamish Grubijan

“n -> n”是什么意思？谢谢。 - nunos

糟糕的符号表示法：“n 对应/映射到 n”。 - Hamish Grubijan

我想知道将NFA> R.E. > DFA转换是否可行/有助于简化目的。R.E.=正则表达式 - Hamish Grubijan

这是回答一个不同的问题，因为他已经知道上限是多少。 - Roger Pate

Answer 3

进一步扩展Jonathan Graehl的出色答案。

对于A(N)中的每个状态0, 1, ..., N，添加一个标记为c的自环，即您添加以下转换：
0 c-> 0
1 c-> 1
...
N c-> N

然后假设c从状态{S,j,k,...,z} <> {S}观察到时，DFA包含与Jonathan的DFA相同的2^(N+1)个状态。因此，除了空集和DFA具有N+2个状态的情况外，所有{S,0,...,N}的子集都是可能的，而DFA具有2^(N+2)-1个状态。

- Alessandro Giua

Answer 4

将N视为函数，其起始状态为S，终止状态为N，该NFA A(N)：

S a-> S
S b-> S
S a-> 0 // NOTE: only "a" allows you to leave state S
0 a-> 1
0 b-> 1
1 a-> 2
1 b-> 2
...
N-1 a-> N
N-2 b-> N
N

显然，这个接受所有字符串[ab]*，其倒数第N个字母为a。

A(N)的确定化必须记住之前的N-1个字母（你需要知道该窗口中所有位置上的a，以便当字符串意外结束时，你可以判断N个字母前是否有a）。

我不确定这是否正好符合您想要的状态数量，但至少是在因子2范围内 - 所有的{0,...,N}子集都是可能的，但你也总是在S。这应该是2^(N+1)个状态，但A(N)有N+2个状态。

- Jonathan Graehl