自动机

下图所示的有限自动机中，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为终态)，该自动机识别的字符串集合可用正规式()来表示

• A.（1|2）*00
• B.（1|2）*0
• C.（0|1|2）*
• D.00（1|2）*

有限状态自动机可用五元组(∑，Q，δ，q0，Qf)来描述，设有一个有限状态自动机M的定义如下：∑={0,1}，Q={q0，q1，q2}，Qf={q2}，δ定义为：δ(q0，0)=q1，δ(q1，0)=q2，6(q2，0)=q2，δ(q2，1)=q2。M是一个(28)有限状态自动机，所表示的语言陈述为(29)。

(51)

A．歧义

B．非歧义

C．确定的

D．非确定的

有限自动机(FA)可用于识别高级语言源程序中的记号(单词)，FA可分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。若某DFA D与某NFA M等价，则(48)。

A．DFA D与NFA M的状态数一定相等

B．DFA D与NFA M可识别的记号相同

C．NFA M能识别的正规集是DFA D所识别正规集的真子集

D．DFA D能识别的正规集是NFA M所识别正规集的真子集

Chomsky定义的四种形式语言文法中，2型语言可由()识别。

A、短语结构文法

B、前后文无关文法

C、前后文有关文法

D、正规文法

E、图灵机

F、有限自动机

G、下推自动机

有限自动机（FA）可用于识别高级语言源程序中的记号（单词），FA 可分为确定的有限自动机（DFA）和不确定的有限自动机（NFA）。若某DFA D 与某NFA M等价，则 （48） 。

（48）

A. DFA D 与NFA M的状态数一定相等

B. DFA D 与NFA M可识别的记号相同

C. NFA M能识别的正规集是DFA D 所识别正规集的真子集

D. DFA D 能识别的正规集是NFA M所识别正规集的真子集

某一确定有限自动机(DFA)的状态转换图如下图，与该自动机等价的正规表达式是(28)，图中(29)是可以合并的状态。

(56)

A．ab*a

B．ablab*a

C．a*b*a

D．aa*lb*a

有限自动机（FA）可用于识别高级语言源程序中的记号（单词），FA 可分为确定的有限自动机（DFA）和不确定的有限自动机（NFA）。若某DFA D 与某NFA M等价，则（）。

对高级语言源程序进行编译的过程中，有穷自动机（NFA或DFA）是进行（49）的适当工具。

A.词法分析

B.语法分析

C.语义分析

D.出错处理

有限状态自动机可用5元组(VT，Q，δ，q0，Qf)来描述，它可对应于(28)。设有一有限状态自动机M的定义如下：

VT＝{0，1}，Q＝{q0，q1，q2)

δ定义为：

δ(q0，0)=q1δ(q1，0)=q2

δ(q2，1)=q2δ(q2，1)=q2

Qf={q2}。

M是一个(29)有限状态自动机，它所对应的状态转换图为(30)，它所能接受的语言可以用正则表达式表示为(31)，其含义为(32)。

A．0型文法

B．1型文法

C．2型文法

D．3型文法

某一确定有限自动机(DFA)的状态转换图如下，与该自动机等价的正规表达式是(28)，图中(29)是可以合并的状态。

(42)

A．(a|ba)*bb(a*b*)*

B．(a|ba)*bba*|b*

C．(a*|b*)bb(a|b)*

D．(a|b*)*bb(a*|b*)

●文法G=(VT，VN，P，S)的类型由G中的 (32) 决定。若G0=({a,b}，{S，X，Y}，P，S)，P中的产生式及其序号如下：

1：S→XaaY

2：X→YYlb

3：Y→XbXla

则G0为 (33) 型文法，对应于 (34) ，由G0推导出句子aaaaa和baabbb时，所用产生式序号组成的序列分别为 (35) 和 (36) 。

(32) A．VT

B．VN

C．P

D．S

(33) A．0

B．1

C．2

D．3

(34) A．图灵机

B．下推自动机

C．有限状态自动机

D．其他自动机

(35),(36) A．13133

B．12312

C．12322

D．12333