0

标题说明了一切。我需要一些想法。nfa 输入看起来像这样，并且没有 epsilon 移动。

1 2
0 a 2
1 b 3

等等，这意味着 1 和 2 是最终状态，而使用“a”我可以从状态 0 到状态 2。

我用

struct nod
{
int ns;
char c;
};

vector<nod> v[100];

保存数据，其中 v[i] 是包含从状态 i 出发的所有路径的向量。 当有多个状态时，我需要一个关于如何命名新状态的想法

0 a 1
0 a 2
0 a 3

因为我无法创建状态 123 或类似的东西。 我如何检查一个多重集是否已经转换为一个状态？

4

1 回答 1

0

在最坏的情况下，具有 n 个状态的 NFA 将需要具有 2^n 个状态的 DFA：一个状态对应于 NFA 中的每个状态子集。另一种思考方式是，如果 NFA 的第 k 个状态包含在 DFA 状态对应的子集中，则 DFA 的所有状态都可以用长度为 n 的二进制字符串标记，其中第 k 位设置为 1。

好的，这可能是一个密集的解析解释。一个例子会有所帮助。假设 NFA 有状态 0、1 和 2。有 2^3 个状态子集，所以我们的 DFA 最多有 8 个状态。位串如下：

  • 000：空集，不包含任何状态
  • 001：只包含状态0的集合
  • 010：仅包含状态 1 的集合
  • 100：仅包含状态 2 的集合
  • 011：包含状态 0 和 1 的集合
  • 101：包含状态 0 和 2 的集合
  • 110：包含状态 1 和 2 的集合
  • 111：包含所有状态的集合

我们可以将这些位串本身解释为整数，这为我们提供了一种标记 DFA 状态的自然方法：

  • 0：空集，不包含任何状态
  • 1：仅包含状态 0 的集合
  • 2：仅包含状态 1 的集合
  • 3：仅包含状态 2 的集合
  • 4：包含状态 0 和 1 的集合
  • 5：包含状态 0 和 2 的集合
  • 6：包含状态 1 和 2 的集合
  • 7：包含所有状态的集合

这种排序的唯一问题是，如果您最终不需要所有状态（通常您不需要），那么您可能在使用的状态之间存在（有时很大）间隙。您的 DFA 可能只需要状态 1、2 和 3（例如，如果您的 NFA 恰好已经是最小 DFA）。也许您只需要状态 1 和 7。存在其他可能性。

如果您是按需创建状态，则始终可以将所创建状态的名称和索引分开。如果您已经创建了 k 个状态，并且您在发现需要时创建了一个新状态，则可以为其分配索引 k+1 并根据位串命名。这样，您的索引就密集地打包在一起，并且您可以通过名称追溯到 NFA 状态的子集。

当有多个状态时，我需要一个关于如何命名新状态的想法

根据相应子集的位串命名它们。

我如何检查一个多重集是否已经转换为一个状态？

检查现有状态以查看您遇到的子集的位字符串是否已被使用。

于 2017-05-05T13:46:01.833 回答