下载APP
【单选题】
（4）处填（）。
A．确定的有限自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有限自动机
E．有限自动机
F．线性有限自动机
A.
根据乔姆斯基20世纪50年代建立的形式语言的理论体系，语言的文法被分为四种类型，即：0型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与（3）等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价（4）。从文法描述语言的能力来说，（5）最强，（6）最弱，由四类文法的定义可知：（7）必是2型文法。
参考答案：
参考解析：
刷刷题刷刷变学霸
举一反三
【单选题】下列关于图灵机的叙述中，错误的是( )。
A.
图灵机有一个无限延长的带子，理论上可以处理连续对象
B.
图灵机不能计算的函数必须由电子计算机来完成计算
C.
图灵机的工作原理蕴含了存储程序的思想
D.
凡是可计算的函数，理论上都可以用图灵机实现
【单选题】3（） A．图灵机 B．下推自动机 C．有穷状态自动机 D．线性界限自动机
A.
在形式语言中，文法G是一个四元组G=(VN，Vr，P，Z)，其中VN为 (1) 。若文法C的产生式集P为：
B.
(1)Z→Bc (2)Z→Zc (3)B→Ab (4)B→Bb (5)A→Aa (6)A→a
C.
则文法G是 (2) 文法，识别G的自动机为 (3) 。对于G来说， (4) 为文法G可接受的字符串， (5) 为文法G不可接受的字符串。
D.
供选择的答案：
【单选题】（4）处填（）。 A．确定的有限自动机 B．图灵机 C．非确定的下推自动机 D．非确定的有限自动机 E．有限自动机 F．线性有限自动机
A.
根据乔姆斯基20世纪50年代建立的形式语言的理论体系，语言的文法被分为四种类型，即：0型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与（3）等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价（4）。从文法描述语言的能力来说，（5）最强，（6）最弱，由四类文法的定义可知：（7）必是2型文法。
【单选题】（67）处填（）。 A．下推自动机 B．线性有界自动机 C．图灵机 D．有穷状态自动机
A.
文法G=(E,+,*,(,),a,P,E)，其中P由下列产生式组成E->E+E|E*E|(E)|a.它生成由a,+,*,(,)组成的算术表达式，该文法在乔姆斯基分层中属于 (66) 型文法，其对应的自动机是 (67) ，如产生句子a*a+a，它的派生树是 (68) ，且最左派生由 (69) 种，该文法是 (70) 。
相关题目：
【判断题】下推自动机所对应的文法为0型文法。
A.
正确
B.
错误
【判断题】图灵机是一个五元组理论模型。
A.
正确
B.
错误
【判断题】图灵机和现在的计算机结构不同
A.
正确
B.
错误
【单选题】下列关于图灵机的叙述中，错误的是( )。
A.
图灵机有一个无限延长的带子，理论上可以处理连续对象
B.
图灵机不能计算的函数必须由电子计算机来完成计算
C.
图灵机的工作原理蕴含了存储程序的思想
D.
凡是可计算的函数，理论上都可以用图灵机实现
【判断题】图灵机可以用2型文法描述
A.
正确
B.
错误
【单选题】1936 年提出“图灵机”的数学家图灵是( )人。
A.
英国
B.
美国
C.
德国
D.
意大利
【判断题】图灵机能够模拟计算机,但计算机难以模拟图灵机。( )
A.
正确
B.
错误
【判断题】通用图灵机模型是计算机的计算能力的极限。
A.
正确
B.
错误
【单选题】积自动机接受的语言为原来两个语言的（）
A.
交
B.
并
C.
连接
D.
对应翻转语言的交
【单选题】3（） A．图灵机 B．下推自动机 C．有穷状态自动机 D．线性界限自动机
A.
在形式语言中，文法G是一个四元组G=(VN，Vr，P，Z)，其中VN为 (1) 。若文法C的产生式集P为：
B.
(1)Z→Bc (2)Z→Zc (3)B→Ab (4)B→Bb (5)A→Aa (6)A→a
C.
则文法G是 (2) 文法，识别G的自动机为 (3) 。对于G来说， (4) 为文法G可接受的字符串， (5) 为文法G不可接受的字符串。
D.
供选择的答案：
【单选题】不能被图灵机求解的问题是( )
A.
可以用计算机求解
B.
不可以用计算机求解
C.
虽可以被计算机计算，但无法设计出算法
D.
与是否能设计出算法无关
【单选题】关于图灵机的描述正确的是（ ）
A.
图灵机是一种思想模型
B.
图灵机就是第一台计算机
C.
图灵机是类似于计算机的可进行计算的工具
D.
图灵机早被淘汰了
【单选题】（4）处填（）。 A．确定的有限自动机 B．图灵机 C．非确定的下推自动机 D．非确定的有限自动机 E．有限自动机 F．线性有限自动机
A.
根据乔姆斯基20世纪50年代建立的形式语言的理论体系，语言的文法被分为四种类型，即：0型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与（3）等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价（4）。从文法描述语言的能力来说，（5）最强，（6）最弱，由四类文法的定义可知：（7）必是2型文法。
【单选题】以下哪个操作不是图灵机的基本操作_。
A.
左移和右移
B.
加法
C.
翻转0为1
D.
停机
【单选题】用于向图灵机器人API服务器发送HTTP请求的是( )
A.
OKHttpSever
B.
OKHttp
C.
RequestBody
D.
HttpRequest
【单选题】（67）处填（）。 A．下推自动机 B．线性有界自动机 C．图灵机 D．有穷状态自动机
A.
文法G=(E,+,*,(,),a,P,E)，其中P由下列产生式组成E->E+E|E*E|(E)|a.它生成由a,+,*,(,)组成的算术表达式，该文法在乔姆斯基分层中属于 (66) 型文法，其对应的自动机是 (67) ，如产生句子a*a+a，它的派生树是 (68) ，且最左派生由 (69) 种，该文法是 (70) 。
【多选题】图灵机由( )几部分组成。
A.
一个状态寄存器
B.
一条可无限衍生的纸带
C.
一个在纸带上左右移动的读写头
D.
一套控制规则
E.
一个存储器