第十三章 图灵机的扩展--习题【含答案】 软件理论基础

(1)单选题

下列自动机中表达能力最弱的为()

A  标准图灵机

B  多带图灵机

C  空栈接受的下推自动机

D  受限图灵机

(2)单选题

至少需要()个栈的多栈机才能模拟出图灵机。

A  2

B  3

C  4

D  5

(3)单选题

被图灵机接受的语言为()

A  递归可枚举语言

B  递归语言

C  正则语言

D  上下文无关语言

(4)单选题

判断下列说法是否正确:非确定的图灵机表达能力强于标准的确定图灵机。

A  正确

B  错误

(5)单选题

以下哪种图灵机在接受{a^n b^n}中的字符串的时间复杂度最低()

A  标准图灵机

B  受限图灵机

C  多带图灵机

D  非确定型图灵机

(6)单选题

判断下列说法是否正确:k 个带的图灵机可以用 2k 个道的图灵机来模拟。

A  正确

B  错误

获取标准答案请阅读全文

隐藏内容 需要支付:¥6

未经允许不得转载!第十三章 图灵机的扩展--习题【含答案】 软件理论基础