维基百科指出,确定性状态自动化“为每个输入字符串生成自动机的唯一计算(或运行)”。
我一直理解这一点,因为只有 1 条可能的路径来计算任何唯一的字符串。在这种情况下,以下是 DSM。
但现在我对此想得太多了,并将描述解释为每个输入字符串都有一个可能的路径,并且该路径与所有其他输入字符串都是唯一的。在这种情况下,以下内容不是 DSM,因为“11”和“12”遵循相同的路径。
所以我的问题是,以下是 DSM 还是 NDSM?
最佳答案
它仍然是确定性的,每个状态的每个输入只有一个可能的路径。 1和2只能返回到自身,因为它是不确定的,输入应该有多个可能的路径。例如,如果输入 1 有从一个特定状态分支的两种可能状态。
简而言之,如果特定输入没有分支路径,并且没有ε-edges在图中,它应该是确定性的。即没有分支路径,我们可以确定它的去向。您在上面绘制的路径我们始终可以确定特定输入的路径。
关于state - 自循环上的两个输入,确定性或非确定性状态机?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10304686/