问题 单项选择题

下图所示为两个有限自动机M1和M2(A是初态、C是终态),()。

A.M1和M2都是确定的有限自动机

B.M1和M2都是不确定的有限自动机

C.M1是确定的有限自动机,M2是不确定的有限自动机

D.M1是不确定的有限自动机,M2是确定的有限自动机

答案

参考答案:D

解析:

确定有限自动机对每一个可能的输入只有一个状态的转移。非确定有限自动机对每一个可能的输入可以有多个状态转移,接受到输入时从这多个状态转移中非确定地选择一个。有限自动机M1在状态A时,输入0可以回到状态A,也可以到达状态B,可见M1是不确定的。有限自动机M2的每个状态下的输入都只有一个转移状态。

单项选择题
单项选择题