某一确定性有限自动机(DFA)的状态转换图如图2-2所示，令d=0｜1｜2｜…19，则以下字符串中，不能被该DFA接受的是(9)，与该DFA等价的正规式是(10)。(其中，ε表示空字符。)A．①②③B．①②④C．②③④D．①②③④
题目
某一确定性有限自动机(DFA)的状态转换图如图2-2所示，令d=0｜1｜2｜…19，则以下字符串中，不能被该DFA接受的是(9)，与该DFA等价的正规式是(10)。(其中，ε表示空字符。)
A．①②③
B．①②④
C．②③④
D．①②③④
相似考题
更多“ 某一确定性有限自动机(DFA)的状态转换图如图2-2所示，令d=0｜1｜2｜…19，则以下字符串中，不能被该DFA接受的是(9)，与该DFA等价的正规式是(10)。(其中，ε表示空字符。)A．①②③B．①②④C．”相关问题
-
第1题：
图8-2为一个DFA的状态转换图，与其等价的正规表达式是(31)，在图中状态(32)是可以合并的状态。
A．(0|1)*11(0*1*)*
B．(0|1)*110*|1*
C．(0*1*)11(0|1)*
D．(0*|1*)*11(0*|1*)
正确答案：A
-
第2题：
某一非确定性有限自动机(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)*。 -
第3题：
某一确定有限自动机(DFA)的状态转换图如下图，与该自动机等价的正规表达式是(28)，图中(29)是可以合并的状态。
(56)
A．ab*a
B．ablab*a
C．a*b*a
D．aa*lb*a
正确答案：A
-
第4题：
图2-7为一确定有限自动机(DFA)的状态转换图，与该自动机等价的正规表达式是(14)，图中的(15)是可以合并的状态。
A．[a｜(ba)]*bb(a*b*)*
B．(a｜b)*bba*｜b*
C．(a*b*)bb(a｜b)*
D．(a｜b)*bb(a*｜b*)*
正确答案：A
-
第5题：
某确定性有限自动机(DFA)的状态转换图如下图所示，令d=0|1|2|…|9，则以下字符串中，能被该DFA接受的是(22)。
A．3857
B．1.2E+5
C．-123.67
D．0.576E10
正确答案：C
解析：本题程序语言翻译基础知识。翻译高级语言源程序的第一步工作是进行词法分析，即将源程序中的单词(记号)识别出来，该过程可用有限自动机描述。自动机M识别一个字符串的过程是从开始状态出发，根据字符串中的字符依次进行状态转移，若能到达终态且字符串结束，则该字符串可被自动机M识别。考查题目中的选项，3857的识别过程是状态0→状态1→状态1→状态1，状态1不是终态；字符串1.2E+5中的“+”不能识别；字符串0.576E10的识别过程是状态0→状态1→状态5→状态6→状态6，在状态6下不能识别E。字符串-123.67的识别过程是状态0→状态4→状态1→状态1→状态5→状态6→状态6，因此该字符串可被厦中的自动机识别。 -
第6题：
某一确定有限自动机(DFA)的状态转换图如下图所示，该DFA接受的字符串集是(28)，与之等价的正规式是(29)。
A．以1开头的二进制代码串组成的集合
B．以1结尾的二进制代码串组成的集合
C．包含偶数个0的二进制代码串组成的集合
D．包含奇数个0的二进制代码串组成的集合
正确答案：C
解析：分析题日中给出的状态转换图可知，状态q0为唯一的终态，因此该DFA可识别空串。以一个。离开状态q0然后再以一个0返回q0，因此，该自动机识别的串是包含偶数个0的二进制代码串。正规式中的运算符“|”、“.”、“*”分别称为“或”、“连接”和“闭包”。在正规式的书写中，连接运算符“.”可省略。运算的优先级从高到低顺序排列为：“*”、“.”、“|”。正规式1*0(0|1)*、((0|1*0)*1*)*、1*((0|1)0)*都没布表示出偶数个零的特点，因此包含偶数个0的二进制代码串的正规式为(1*(01*0)*)*。 -
第7题：
某确定的有限自动机 (DFA) 的状态转换图如下图所示 (A 是初态，D、E 是终态)，则该 DFA 能识别（ ）。
A.00110B.10101C.11100D.11001
正确答案：C
-
第8题：
某一非确定性有限自动机(NFA)的状态转换图如图2-6所示，与该NFA等价的正规式是(12)，与该NFA等价的DFA是(13)。
A．0*｜(0｜1)0
B．(0｜10)*
C．0*[(0｜1)0]*
D．0*(10)*
正确答案：B
-
第9题：
某非确定的有限自动机（NFA）的状态转换图如下图所示（q0既是初态也是终态），与该NFA等价的确定的有限自动机（DFA）是 （ ） 。
答案：A解析：本题考查有限自动机这一知识点。容易看出，能被题中不确定的有限自动机接受的符号串有两种情形，一种是???表示的符号串，另一种是(ba)?符号串。在四个选项中，只有A选项的有限自动机能同时接受???和(ba)?这两种符号串，故本题选择A选项。 -
第10题：
某一非确定性有限自动机（NFA）的状态转换图如下图所示，与该NFA等价的正规式是（ ），与该NFA等价的DFA是（请作答此空）。
答案：A解析： -
第11题：
某一确定有限自动机(DFA.的状态转换图如下图所示，该DFA接受的字符串集是 ( ) ，与之等价的正规式是 (请作答此空) 。
A.1*0(0|1)*
B.((0|1*0)*1*)*
C.1*((0|1)0)*
D.(1*(01*0)*)*答案：D解析：分析题日中给出的状态转换图可知，状态q0为唯一的终态，因此该DFA可识别空串。以一个。离开状态q0然后再以一个0返回q0，因此，该自动机识别的串是包含偶数个0的二进制代码串。正规式中的运算符“|”、“•”、“*”分别称为“或”、“连接”和“闭包”。在正规式的书写中，连接运算符“•”可省。运算的优先级从高到低顺序排列为：“*”、“•”、“|”。正规式1*0(0|1)*、((0|1*0)*1*)*、1*((0|1)0)*都没布表示出偶数个零的特点，因此包含偶数个0的二进制代码串的正规式为(1*(01*0)*)*。 -
第12题：
下图所示为一个不确定有限自动机（NFA）的状态转换图，与该NFA等价的 DFA是（ ）
答案：C解析：NFA可以有000状态，因此排除A；NFA可以有010状态，可以排除BD。 -
第13题：
某一非确定性有限自动机(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
-
第14题：
某一确定有限自动机(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
-
第15题：
● 某确定性有限自动机（DFA）的状态转换图如下图所示，令 d=0|1|2|...|9，则以下字符串中，能被该DFA 接受的是 （49） 。
（49）
A. 3857
B. 1.2E+5
C. -123.67
D. 0.576E10
正确答案：C
-
第16题：
某一确定性有限自动机(DFA)的状态转换图如下图所示，令d=0|1|2|…|9，则以下字符串中，不能被该DFA接受的是(33)，与该DFA等价的正规式是(34)。(其中，ε表示空字符)
①3857
②1.2E+5
③-123．
④.576E10
A．①、②、③
B．①、②、④
C．②、③、④
D．①、②、③、④
正确答案：B
解析：有限自动机也称为有穷状态自动机，是一种数学机器模型，基本形式有非确定有限自动机(NFA)和确定的有限自动机(DFA)，并且每一个NFA都有与其等价的DPA。有穷状态自动机的物理模型如下图所示。
[*]
一个DFA可以用状态转换图直观的方式。状态转换图是一种有向图。DFA中的每个状态对应转换图中的一个节点，从外部引入弧的节点表示开始节点，双圈节点表示终态；DFA中的每个状态转换对应图中的一条有向弧，若转换关系为/(A,a)=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。有穷状态自动机识别字符串的过程为：初始时，机器处于起始状态(题图中节点。表示初始状态)。读取一个输入符号，并进行相应的状态转移，直到输入串结束或找不到相应的状态转移时为止。根据题目终给定的自动机，识别3857、1.2E+5、-123.、.576E10的过程分别如下。
[*]
分析题中给定的有穷状态自动机，可知该自动机识别以下形式的数值：带小数部分的十进制表示形式和以尾数、指数表示的数值形式。其中，从初态0到达终态5所识别的是带小数点的以十进制数值表示形式的字符串，小数点后可以没有数字，也可以有若干个数字，而小数点之前的整数部分可以不带符号，也可以带负号，其正规式为“(-d|d)d*.d*。当数值的表示含有指数部分时，指数部分是不带符号(表示正数)或带负号的整数形式，因此该部分的正规式为“E(-d|d)d*”。 -
第17题：
有限自动机(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所识别正规集的真子集
正确答案：B
解析：本题考查程序语言翻译基础知识。非确定有限自动机NFA是一个五元组(5-tuple)：M=(S，∑，move，s0，F)其中，①S是有限个状态(state)的集合；②∑是有限个输入字符(包括ε)的集合：③move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态即④sj；④s0是唯一的初态(也称开始状态)；⑤F是终态集(也称接受状态集)，它是S的子集，包含了所有的终态。确定的有限自动机DFA是WA的特例：①DFA没有状态具有ε状态转移(ε-transition)，即状态转换图中没有标记ε的边；②对每一个状态s和每一个字符a，最多有一个下一状态。若两个FA识别同一个正规集，则这两个FA等价。对于每个NFA，都存在与之等价的DFA。 -
第18题：
某一确定有限自动机(DFA)的状态转换图如图2-1所示，该DFA接受的字符串集是(7)，与之等价的正规式是(8)。
A．以1开头的二进制代码串组成的集合
B．以1结尾的二进制代码串组成的集合
C．包含偶数个0的二进制代码串组成的集合
D．包含奇数个0的二进制代码串组成的集合
正确答案：C
-
第19题：
某确定的有限自动机(DFA)的状态转换图如下图所示(A是初态，C是终态)，则该DFA能识别()。
A.aabb
B.abab
C.baba
D.Abba
正确答案：B
-
第20题：
若将有限状态自动机(DFA)识别的0、1符号串看作二进制数，则(6)识别的是能被十进制数3整除的正整数，(7)是与该自动机等价的正规式。
A．
B．
C．
D．
正确答案：A
解析：任何一个整数被3除后，余数或为0、或为1、或为2。因此，若将该DFA识别的0、 1串看作是二进制整数，则有以下结论：
▲ 0被3除，余数为0。
▲ 设能被3整除的二进制数为x。若在x之后连接一个0所得的数为y，则y=2x，且y被3整除的余数仍然为0。若在x之后连接一个1所得的数为y，则y=2x+1，因此， y被3整除的余数将等于1。
▲ 设被3整除后余数为1的二进制数为x。若在x之后连接一个0所得的数为y，则y=2x，且y被3整除的余数为2。若在x之后连接一个1所得的数为y，则y2x+l，且y被3整除的余数将等于0。 ‘
▲ 设被3整除后余数为2的二进制数为x。若在x之后连接一个0所得的数为y，则y=2x，且y被3整除的余数为1。若在x之后连接一个1所得的数为y，则y=2x+l，且y被3整除的余数仍等于2。
综上，设被3除后的余数为0用qo(下标)表示、余数为1用q1(下标)表示、余数为2用q2(下标)表示，若将空串的值看作0，则下图所示的自动机识别的是能被3整除的整数，其正规式为(0* (1(01*0)*1)*)*。
若限定该自动机识别的0、1序列不能为空串，则相应自动机的状态转换图如下图所示。
-
第21题：
某一非确定性有限自动机（NFA）的状态转换图如下图所示，与该NFA等价的正规式是（请作答此空），与该NFA等价的DFA是（ ）。
A.0*|（0|1）0
B.（0|10）*
C.0*（（011）0）*
D.0*（10）*答案：B解析： -
第22题：
下图所示为一个不确定有限自动机的状态转换图，与该NFA等价的DFA是（ ）。
答案：C解析：本题可以直接以实例方式排除错误选项。本题给出的NFA，能够识别字符串000,010等，以这两个字符串为例进行分析。与之等价的DFA，也必须能够识别这样的串。A选项不能识别000，B选项不能识别010，D选项不能识别010.只有C选项能够同时识别这2个串，因此本题选择C选项 -
第23题：
某确定的有限自动机（DFA）的状态转换图如下图所示（0 是初态，4 是终态），则该 DFA能识别（49）。
A.aaab
B.abab
C.bbba
D.abba答案：A解析：将选项分别带入判断。