state - 自循环，确定性或非确定性状态机上的两个输入？

Question

维基百科指出，确定性状态自动化“为每个输入字符串生成自动机的唯一计算(或运行)”。

我总是理解这一点，因为只有 1 个可能的路径来计算任何唯一的字符串。在这种情况下，以下是 DSM。

但是现在我想太多了，并将描述解释为每个输入字符串都有一个可能的路径，并且该路径与所有其他输入字符串是唯一的。在这种情况下，以下不是 DSM，因为“11”和“12”遵循相同的路径。

所以我的问题是，以下是 DSM 还是 NDSM？

Answer 1

它仍然是确定性的，每个状态的每个输入只有一个可能的路径。 1、2只能回到自身，因为它是不确定的，输入应该有多个可能的路径。例如，如果输入 1 具有从一种特定状态分支的两种可能状态。

简而言之，如果特定输入没有分支路径，并且没有 ε-edges在图中，它应该是确定性的。即没有分支路径，我们可以确定它去哪里。您在上面绘制的那个我们总是可以确定特定输入的路径。