自动机
以下关于语言L={anbn|n>=1}的叙述中，正确的是（）。
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下有关文法)、2型(上F文无关文法)和3型(正规文法)。其中，2型文法与(56)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(57)。从文法描述语言的能力来说，(58)最强，(59)最弱，山4类文法的定义可知：(60)必是2型文法。
A．确定的有限自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有限自动机
E．有限自动机
●根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(28)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(29)。从文法描述语言的能力来说，(30)最强，(31)最弱，由4类文法的定义可知：(32)必是2型文法。
(28)A．线性有限自动机
B．非确定的下推自动机
C．图灵机
D．有限自动机
(29)A．确定的有限自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有限自动机
(30)A．1型文法
B．2型文法
C．3型文法
D．0型文法
(31)A．3型文法
B．2型文法
C．0型文法
D．1型文法
(32)A．1型文法
B．0型文法
C．3型文法
D．2型文法
根据乔姆斯基20世纪50年代建立的形式语言的理论体系，语言的文法被分为四种类型，即：O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(67)。从文法描述语言的能力来说，(68)最强，(69)最弱，由四类文法的定义可知：(70)必是2型文法。
(40)
A．确定的有限自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有限自动机
E．有限自动机
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，文法被分为4种类型，即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(1)等价，所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的有穷自动机必存在一个与之等价的(2)。从文法描述语言的能力来说，(3)最强，(4)最弱，由4类文法的定义可知(5)必是2型文法。
A．确定的有穷自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有穷自动机
E．有穷自动机
下面哪个不是单词的描述工具？（）
A、正规式
B、有穷自动机
C、下推自动机
D、正规文法
一个有限自动机识别的语言是一个无限集合，则该有限自动机的状态图一定含有回路。（)
此题为判断题（对，错)。
构造识别单词的有限自动机时，先要对程序语言的单词按类构造出相应的有限自动机。（)
此题为判断题（对，错)。
（）信息反馈系统是当前信息工作中的主要反馈系统。
A．人工
B．自动机
C．人工一自动机复合
D．计算机
下图所示的有限自动机中，0是初始状态，3是终止状态，该自动机可以识别(22)。
A．abab
B．aaaa
C．bbbb
D．abba
下图所示的有限自动机中，s0是初始状态，s1为终止状态，该自动机不能识别()。
A．abab
B．aaaa
C．babb
D．abba
任意有限自动机都能转化为_等价的特殊自动机：其状态图中初态无射人弧，终态无射出弧。（)
此题为判断题（对，错)。
●文法G=({E}，{+，*，(，)，a}，P，E)，其中P由下列产生式组成E->E+E｜E*E｜(E)｜a。它生成由a，+，*，(，)组成的算术表达式，该文法在乔姆斯基分层中属于(33)型文法，其对应的自动机是(34)，如产生句子a*a+a，它的派生树是(35)，且最左派生由(36)种，该文法是(37)。
(33)A．0
B．1
C．2
D．3
(34)A．下推自动机
B．线性有界自动机
C．图灵机
D．有穷状态自动机
(35)A．二叉树
B．完全有界自动机
C．三叉树
D．四叉树
(36)A．0
B．1
C．2
D．3
(37)A．非二义性
B．二义性
C．单一性
D．多义性
某有限状态自动机的状态图如图2-4所示（状态0是初态，状态2是终态），则该自动机不能识别（）。
A、abab
B、aabb
C、bbaa
D、bbab
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(28)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(29)。从文法描述语言的能力来说，(30)最强，(31)最弱，由4类文法的定义可知：(32)必是2型文法。
A．线性有限自动机
B．非确定的下推自动机
C．图灵机
D．有限自动机
将识别各类单词的有限自动机合并后得到的有限自动机_______。
A．可能是NFA也可能是DFA
B．一定是DFA
C．一定是NFA
D．是最小的DFA
若将有限状态自动机(DFA)识别的0、1符号串看做二进制数，则自动机(27)识别的是能被十进制数3整除的正整数。
A．
B．
C．
D．
下图是一个有限自动机的状态转换图(A为初态，C为终态)，该自动机识别的字符串集合可用正规式()来表示