下列自动机中表达能力最弱的为()
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 错误
获取标准答案请阅读全文
未经允许不得转载!第十三章 图灵机的扩展--习题【含答案】 软件理论基础