computer-science - NFA 到 DFA 问题

Question

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

已知（并证明）一个 NFA 的等效 DFA 最多有 2 ⁿ个状态，尽管大多数时候它的状态数与 NFA 或多或少相同。

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

我提出这个问题的原因是能够“发明”一些 NFA，这些 NFA 肯定会在不考虑最小化的情况下产生 2 ⁿ - 1 个状态加上“死状态”。

Answer 1

由于非确定性，状态数量激增，这是您问题的关键。

如果您采用 NFA，其中每个转换都是唯一确定的，即确定性 NFA，那么它只不过是一个正常的 DFA。但是，一旦您有可能进行两次转换的状态，它就与 DFA 不同。

考虑转换算法，看看如果您有两个或多个具有相同标签的状态转换会发生什么。这是您需要与状态集相对应的那些新状态的地方。

所以问题归结为找出这些超集状态中有多少实际上是可以到达的。当然，您可以为此发明一种奇特的算法，但要获得正确的数字，只需运行正常的转换算法并删除无法到达的状态。

对于具有 n 个状态的 NFA，其等效 DFA 具有 2^n 个状态，请考虑利用非确定性。第一个想法是将所有转换标记为相同，但是效果不太好。相反，请记住，您需要能够以某种方式到达所有状态子集，每个子​​集都带有一些标签。

如果不计算起始状态，则可以执行以下构造：创建 n 个节点，并为 2^n 中的每个集合创建一个唯一标签，并在 NFA 中为该集合的每个节点添加一个带有此标签的转换。这为您提供了具有 n+1 个状态的 NFA（1 是起始状态），其中 DFA 需要 2^n+1 个状态。当然，一旦你想在最小化后拥有 2^n 个 DFA 状态，它就会变得更加棘手。

Answer 2

好的，从假设 n -> n 开始。现在，对于从一个状态到 x 个其他状态的每个非确定性转换，将您的估计值乘以 x。这可能不准确，因为您可能会重复计算。但它应该给你一个上限。

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

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

Answer 3

作为 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，以便当字符串意外结束时，您可以说出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状态。