math - 确定非确定性有限自动机是否接受所有可能的字符串

Question

给定一个 NFA，有没有办法确定它是否接受从其字母表构造的所有字符串，而不必遍历无限的可能字符串集？

Answer 1

当然！这是一种算法：

1. 运行子集构造以将 NFA 转换为 DFA。
2. 使用 DFA 最小化算法最小化 DFA。
3. 检查 DFA 是否包含一个正在接受的状态。如果是这样，原来的 NFA 接受一切。如果不是，则至少有一个 NFA 不接受的字符串。

可能有比这更快的算法（步骤（1）可能需要输入 NFA 大小的指数时间），但这表明确实有一些算法可以解决这个问题。