NFA转化为DFA =确定性？

Question

我在决定论和非决定论的意义上挣扎了一下。当涉及到自动机时，我得到了不同，但我似乎无法找到以下答案：NFA转换为DFA转换是否具有确定性？

如果可以为同一常规语言构建多个DFA，那么这是否意味着NFA转换为DFA的结果不是唯一的？因此一个非确定性算法？

我很高兴你可以提供任何信息。

在此先感谢！

Answer 1

在这里玩有两个不同的概念。首先，你是正确的，可以有许多不同的DFA等价于相同的NFA，就像可以有许多相互等价的NFA一样。

独立地，有几种将NFA转换为DFA的算法。在大多数正式语言入门课程中教授的标准算法是子集构建（也称为powerset构建）。该算法是确定性的 - 将NFA转换为DFA需要遵循特定的步骤顺序，因此，只要您使用同一个NFA，就会始终返回相同的DFA。您可以想象，将NFA转换为DFA的算法可能会产生许多不同的DFA中的一种作为输出，但据我所知，没有任何这种着名的算法。

希望这会有所帮助！