下图所示为一个不确定有限自动机的状态转换图，与该NFA等价的DFA是（）。

题目

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

如图3-1所示为一确定有限自动机(DFA)的状态转换图，与该自动机等价的正规表达式是(1)，图中的(2)是可以合并的状态。

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

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

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

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

正确答案：A
解析：在状态转换图中，每一个结点代表一个状态，其中双圈是终结状态。该题实际上是一个简化确定有限自动机(DFA)的过程，一个确定有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。
首先介绍2个概念：最小状态DFA和等价状态。
最小状态DFA必须满足以下2个条件。
(1)没有多余状态(死状态)：多余状态从该自动机的开始状态出发，任何输入串都不能到达的那个状态。
(2)没有2个状态是互相等价(不可区别)。
2个状态s和t如果同时满足下列2个条件，就称s和t是等价的。
(1)一致性：同是终态或同是非终态。
(2)蔓延性：从s出发读人某个a和从t出发读入某个a到达的状态等价。
本题的简化过程如下：
首先，将图中状态分为终态和非终态2个子集即({0,1},{2,3})，再进行子集划分，观察第一个子集{0,1}，输入b后，状态0转换为状态1，而状态1转换为状态2。因此{1}和{2}中的状态是可区别的。
由于状态2,3输入字符a得到相同的结果3，输入字符b得到相同结果2，所以子集 {2,3}是不可区别的。从而得到新的划分：({0}，{1}，{2，3})，因此，(2)空的正确答案为B。
重复子集划分步骤，发现新的状态无法再次划分。
所以，本题中2，3状态可以消除3状态，得到新的状态转换图如图3-2所示。

第2题：

已知一不确定的有限自动机(NFA)如图2-8所示，采用子集法将其确定化为DFA的过程如表2-1所示。

状态集T1中不包括编号为(23)的状态；状态集T2中的成员有(24)：状态集T3等于(25)；该自动机所识别的语言可以用正规式(26)表示。

A．2

B．4

C．3

D．5

正确答案：A

第3题：

某一确定性有限自动机(DFA)的状态转换图如下图所示，令d=0|1|2|…|19，则以下字符串中，不能被该DFA接受的是(28)，与该DFA等价的正规式是(29)。(其中，ε表示空字符)

①3857

②1.2E+5

③-123．

④.576E10

A．①、②、③

B．①、②、④

C．②、③、④

D．①、②、③、④

正确答案：B
解析：有限自动机也称为有穷状态自动机，是一种数学机器模型，基本形式有非确定有限自动机(NFA)和确定的有限自动机(DFA)，并且每一个NFA都有与其等价的DFA。有穷状态自动机的物理模型如下图所示。

一个DFA可以用状态转换图直观的方式。状态转换图是一种有向图。DFA中的每个状态对应转换图中的一个节点，从外部引入弧的节点表示开始节点，双圈节点表示终态；DFA中的每个状态转换对应图中的一条有向弧，若转换关系为/(A，a)=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。
有穷状态自动机识别字符串的过程为：初始时，机器处于起始状态(题图中节点0表示初始状态)。读取一个输入符号，并进行相应的状态转移，直到输入串结束或找不到
相应的状态转移时为止。
根据题目终给定的自动机，识别3857、1.2E+5、-123.、.576E10的过程分别如下。

分析题中给定的有穷状态自动机，可知该自动机识别以下形式的数值：带小数部分的十进制表示形式和以尾数、指数表示的数值形式。其中，从初态0到达终态5所识别的是带小数点的以十进制数值表示形式的字符串，小数点后可以没有数字，也可以有若干个数字，而小数点之前的整数部分可以不带符号，也可以带负号，其正规式为“(-d|d) d*.d，”。当数值的表示含有指数部分时，指数部分是不带符号(表示正数)或带负号的整数形式，因此该部分的正规式为“E(-d|d)d*”。

第4题：

某一确定有限自动机(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*)

正确答案：A

第5题：

某一非确定性有限自动机(NFA)的状态转换图如图6-1所示，该NFA等价的正规式是(1)，与该NFA等价的DFA是(2)。

A．0*|(0|1)0

B．(0|10)*

C．0*((0|1)0)*

D．0*(10)*

正确答案：B

第6题：

对于下图的NFA，其等价的DFA是(27)。

A．

B．

C．

D．

正确答案：A
解析：对于任何一个NFAM，都存在一个DFAM'，使得L(M')=L(M)从M出发构造M'的方法是：让M'的状态对应M的状态集合，即若δ(q，a)={q1,q2,…，qk}，则集合{q1，q2，…，qk}作为M'中的一个状态，这个方法称为子集构造法。对于图中的NFAM，没有ξ弧，其转换函数如下：δ(0,0)={0，1}δ(0,1)={1}δ(1,0)=δ6(1，1)={0,1}δ({0，1}，0)=δ(0,0)∪δ(1,0)={0，1}δ({0，1}，1)=δ(0,1)∪δ(1，1)={0,1}对上面的状态重新命名，就是被选择答案中的A。

第7题：

某一确定性有限自动机(DFA)的状态转换图如图6-5所示，令d=0|1|2|…|9，则以下字符串中，不能被该DFA接受的是(3)，与该DFA等价的正规式是(4)。 (其中，ε表示空字符)

①3857

②1.2E+5

③-123

④.576E10

A．①、②、③

B．①、②、④

C．②、③、④

D．①、②、③、④

正确答案：B

第8题：

● 有限自动机（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所识别正规集的真子集

正确答案：B

第9题：

某一非确定性有限自动机(NFA)的状态转换图如下图所示，与该NFA等价的正规式是(28)，与该NFA等价的DFA是(29)。

A．0*|(0|1)0

B．(0|10)*

C．0*((0|1)0)*

D．0*(10)*

正确答案：B
解析：根据分析题目中给出的状态转换图可知，该NFA可识别空串以及任意数目0组成的串，但若出现1，则其后至少要有1个0才能到达终态，因此，该自动机识别的串等价于正规式(0|10)*。

第10题：

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

(56)

A．ab*a

B．ablab*a

C．a*b*a

D．aa*lb*a

正确答案：A

下图所示为一个不确定有限自动机的状态转换图，与该NFA等价的DFA是（）。

题目

相似问题和答案

更多相关问题

相关内容

下图所示为一个不确定有限自动机的状态转换图，与该NFA等价的DFA是（ ）。

题目

相似问题和答案

更多相关问题

相关内容

下图所示为一个不确定有限自动机的状态转换图，与该NFA等价的DFA是（）。