能力倾向|门CS 1998 |问题11

关于语言的识别能力，以下哪种说法是错误的？ （A） 非确定性有限状态自动机等价于确定性有限状态自动机。 （B） 非确定性下推自动机等价于确定性下推自动机。 （C） 非确定性图灵机等价于确定性图灵机。 （D） 多磁带图灵机相当于单磁带图灵机。 答复: （B） 说明： 非确定性下推自动机 不等同于确定性下推自动机。

选项（B）是错误的。 这个问题的小测验