给定一个 NFA，有没有办法确定它是否接受从其字母表构造的所有字符串，而不必迭代无限的可能字符串集？
最佳答案
当然!这是一种算法:
- 运行子集构造，将 NFA 转换为 DFA。
- 使用 DFA 最小化算法最小化 DFA。
- 检查 DFA 是否包含单个正在接受的状态。如果是这样，原来的 NFA 会接受一切。如果不是，则至少有一个字符串是 NFA 不接受的。
可能有比这更快的算法(步骤(1)可能需要输入 NFA 大小的指数时间)，但这表明确实有一些算法可以解决这个问题。
关于math - 确定非确定性有限自动机是否接受每个可能的字符串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61545206/