给定任何文档，我希望能够生成一个仅接受文档中存在的单词的 NFA。基本上，我想编写一个能够从任何文档动态生成 NFA 的函数。是否有任何预先存在的算法已经这样做了？
问问题
79 次
1 回答
0
如果你想要的只是一个没有要求的 NFA，那么构建几乎是微不足道的。
对于每个单词 w，使用 |w| 在 NFA 中创建一个不同的分支 + 1 个状态（不包括初始状态）。从起始状态开始，向第一个状态添加一个空转换，然后在 w 的第 n 个字符上添加从第 n 个状态到第 n+1 个状态的转换。使 |w|+1th 状态接受。
这将为您提供一个具有与文件中符号+单词一样多的状态的 DFA。如果您想要更少的状态，您可以通过为所有单词中的所有第一个字母创建第一个“层”，为所有单词中的所有第二个字母创建第二个“层”等来做更多分层的事情，并在层中添加状态的转换如果存在使转换有效的单词 w，则 n 到第 n+1 层中的状态。事实上，如果你做对了，你最终会得到一个 DFA，而且它也可能是最小的（练习：证明或反驳这一点）。
于 2016-09-06T14:38:42.960 回答