NFA到DFA问题

Question

首先，这不是要求算法将NFA转换为DFA的问题。

众所周知（并证明）NFA的等效DFA最多具有2ⁿ 州，即使大多数时候，它也将具有与NFA相同数量的状态数量。

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

我要求这样做的原因是能够“发明”一些肯定会产生的NFA，而无需考虑最小化，2ⁿ -1个状态加上“死状态”。

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状态，它就会变得更加棘手。

Answer 2

好的，从假设N-> n开始。现在，对于每个非确定性过渡，您可以从一个州最终进入x其他状态，将估计值乘以x。这可能并不精确，因为您可能会进行双重计数。但这应该给您上限。

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

最后，您可能可以简化一些DFA（以及此事的NFA），但这是一个全新的故事...

Answer 3

作为n的函数，具有开始状态和最终状态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]* 从last last的nth字母是 a.

确定 A(N) 必须有效地记住以前的N-1字母（您需要知道该窗口中的所有位置 a, ，因此，当弦出意外结束时，您可以说是否有一个 a n前字母）。

我不确定这是否完全达到了您想要的状态，但至少在2倍以内 {0,...,N} 有可能，但你也总是在 S. 。应该是 2^(N+1) 州，但是 A(N) 有 N+2 状态。

Answer 4

进一步扩展了乔纳森·格雷尔（Jonathan Graehl）的出色答案。

添加到每个状态 0, 1, ..., N 的 A(N) 一个标记的自圈 c, ，即，您添加以下过渡：
0 c-> 0
1 c-> 1
...
N c-> N

然后假设 c 永远不要发射，DFA包含相同的 2^(N+1) 乔纳森（Jonathan）的DFA州。但是，无论何时 c 从一个国家观察到 {S,j,k,...,z} <> {S} 我们达到状态 {j,k,...,z}. 。因此，所有的子集 {S,0,...,N} 除了空集和DFA是否有可能 2^(N+2)-1 国家 A(N) 有 N+2 状态。