问题
单项选择题
下图所示为两个有限自动机M1和M2(A是初态、C是终态),()。
A.M1和M2都是确定的有限自动机
B.M1和M2都是不确定的有限自动机
C.M1是确定的有限自动机,M2是不确定的有限自动机
D.M1是不确定的有限自动机,M2是确定的有限自动机
答案
参考答案:D
解析:
确定有限自动机对每一个可能的输入只有一个状态的转移。非确定有限自动机对每一个可能的输入可以有多个状态转移,接受到输入时从这多个状态转移中非确定地选择一个。有限自动机M1在状态A时,输入0可以回到状态A,也可以到达状态B,可见M1是不确定的。有限自动机M2的每个状态下的输入都只有一个转移状态。