niusouti.com
某确定的有限自动机 (DFA) 的状态转换图如下图所示 (A 是初态，D、E 是终态)，则该 DFA 能识别（ ）。A.00110B.10101C.11100D.11001
题目
某确定的有限自动机 (DFA) 的状态转换图如下图所示 (A 是初态，D、E 是终态)，则该 DFA 能识别（ ）。
A.00110B.10101C.11100D.11001
相似考题
更多“某确定的有限自动机 (DFA) 的状态转换图如下图所示 (A 是初态,D、E 是终态),则该 DFA 能识别( )。 ”相关问题
-
第1题：
某一确定性有限自动机(DFA)的状态转换图如图6-5所示，令d=0|1|2|…|9，则以下字符串中，不能被该DFA接受的是(3)，与该DFA等价的正规式是(4)。 (其中，ε表示空字符)
①3857
②1.2E+5
③-123
④.576E10
A．①、②、③
B．①、②、④
C．②、③、④
D．①、②、③、④
正确答案：B
-
第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题：
●下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机识别的语言可用正规式(48)表示。
(48)
A. (0|1)*01
B．1*0*10*1
C．1*(0)*01
D.1*(0|10)*1*
正确答案：A
-
第4题：
下图所示的非确定有限自动机（S0为初态，S3为终态）可识别字符串（）。
A.bbaa
B.aabb
C.abab
D.baba
正确答案：B
-
第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)的状态转换图如图2-2所示，令d=0｜1｜2｜…19，则以下字符串中，不能被该DFA接受的是(9)，与该DFA等价的正规式是(10)。(其中，ε表示空字符。)
A．①②③
B．①②④
C．②③④
D．①②③④
正确答案：B
-
第7题：
某非确定的有限自动机（NFA）的状态转换图如下图所示（q0既是初态也是终态）。以下关于该NFA的叙述中，正确的是（ ）。
A.其可识别的0、1序列的长度为偶数
B.其可识别的0、1序列中0与1的个数相同
C.其可识别的非空0、1序列中开头和结尾字符都是0
D.其可识别的非空0、1序列中结尾字符是1答案：D解析：本题考查程序语言基础知识。若存在一条从初态到某一终止状态的路径，且这条路径上所有弧的标记符连接成的字符串等于ω，则称ω可由NFA识别（接受或读出）。对于题中给出的NFA，其初态为q0，q0上的自回路表示识别零个或多个1，接下来识别出一个0时进入状态q1，q1上的自回路表示识别零个或多个0，接下来识别出1个1之后再回到q0。例如，该自动机可识别空串（因为q0既是初态，也是终态）、01、00001、101、1、11、111、1111等。01的识别路径为q0→q1→q000001的识别路径为q0→q1→q1→q1→q1→q0101的识别路径为q0→q0→q1→q01的识别路径为q0→q011的识别路径为q0→q0→q0111的识别路径为q0→q0→q0→q01111的识别路径为q0→q0→q0→q0→q0识别字符串时必须从初始状态q0出发，并回到状态q[0]，因此对于仅由1构成的任意长度的串，在识别过程中不会离开q0。当识别出一个0而离开q0后就进入q1，此后的字符若全部为0，则会一直在q1，直到识别出一个1而回到q0，因此除了空串，该NFA识别的字符串必须以1结尾。 -
第8题：
下图是一个非确定有限自动机（NFA）的状态转换图，其中，S0为初态，S3为终态，该NFA可识别字符串（）（即找出从初态到终态的路径上所标记的字符序列）
A.0101
B.0011
C.1100
D.1010答案：A解析：判断一个字符串能否被指定的自动机识别,就是在该自动机的状态图中能否找到从开始状态到达终止状态的路径，且路径上的字符串等于需要识别的字符串。 -
第9题：
下图是一个有限自动机的状态转换图（0为初态、3为终态),该自动机可识别字符串（ ）(即找出从初态到终态的路径上所标记的字符序列)。
A.xxyy
B.xyxy
C.yyxx
D.yxyx答案：A解析：选项依次带入，能从初态最后到终态的只有A。 -
第10题：
下图所示为一个不确定有限自动机的状态转换图，与该NFA等价的DFA是（ ）。
答案：C解析：本题可以直接以实例方式排除错误选项。本题给出的NFA，能够识别字符串000,010等，以这两个字符串为例进行分析。与之等价的DFA，也必须能够识别这样的串。A选项不能识别000，B选项不能识别010，D选项不能识别010.只有C选项能够同时识别这2个串，因此本题选择C选项 -
第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题：
某有限状态自动机的状态图如下图所示(状态0是初态，状态2是终态)，则该自动机不能识别______。
A．abab
B．aabb
C．bbaa
D．Bbab
A．
B．
C．
D．
正确答案：A
解析：本题考查程序语言处理基础知识。
对于选项A，从状态图的状态0出发，识别a后到达状态0，识别b后到达状态1，由于不存在从状态1出发识别a的状态转移，因此，abab不能被该自动机识别。
对于选项B，识别aabb的状态转移路是状态0→状态0→状态1→状态2。
对于选项C，识别bbaa的状态转移路是状态0→状态1→状态2→状态2→状态2。
对于选项D，识别bbab的状态转移路是状态0→状态1→状态2→状态2→状态2。 -
第14题：
某一确定有限自动机(DFA)的状态转换图如下图，与该自动机等价的正规表达式是(28)，图中(29)是可以合并的状态。
(56)
A．ab*a
B．ablab*a
C．a*b*a
D．aa*lb*a
正确答案：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题：
● 某有限状态自动机的状态图如下图所示（状态 0是初态，状态2是终态），则该自动机不能识别 （30） 。
(30)
A. abab
B. aabb
C. bbaa
D. bbab
正确答案：A
-
第17题：
某确定的有限自动机(DFA)的状态转换图如下图所示(A是初态，C是终态)，则该DFA能识别()。
A.aabb
B.abab
C.baba
D.Abba
正确答案：B
-
第18题：
下图所示的非确定有限自动机 （S0为初态，S3为终态）可识别字符串（ ）。
A. bbaa
B.aabB.
C.abab
D. babA.答案：B解析： -
第19题：
下图是一个有限自动机的状态转换图（A为初态、C为终态），该自动机识别的字符串集合可用正规式（ ）来表示。
A.（1|2）*00
B.0（1|2）*0
C.（0|1|2）*
D.00（1|2）*答案：B解析：一个有限自动机所识别的语言是从开始状态到终止状态所有路径上的字符串的集合。要判断一个字符串能否被指定的自动机识别，就看在该自动机的状态图中能否找到一条从开始状态到达终止状态的路径，且路径上的字符串等于需要识别的字符串。从图中看，首先要识别字符0，然后最终要识别的也是字符0，中间识别1或者2，可以0次或者无穷次。 -
第20题：
某非确定的有限自动机（NFA）的状态转换图如下图所示（q0既是初态也是终态），与该NFA等价的确定的有限自动机（DFA）是 （ ） 。
答案：A解析：本题考查有限自动机这一知识点。容易看出，能被题中不确定的有限自动机接受的符号串有两种情形，一种是???表示的符号串，另一种是(ba)?符号串。在四个选项中，只有A选项的有限自动机能同时接受???和(ba)?这两种符号串，故本题选择A选项。 -
第21题：
某一非确定性有限自动机（NFA）的状态转换图如下图所示，与该NFA等价的正规式是（ ），与该NFA等价的DFA是（请作答此空）。
答案：A解析： -
第22题：
下图所示的非确定有限自动机（So为初态，S3为终态）可识别字符串（ ）
A.bbaa
B.aabb
C.abab
D.baba答案：B解析：本题考查程序设计语言中简单算法的知识。对于S0来说，输入任意的a都可以，也可以输入任意的b，但必须有一个a才能到达状态S1, 但是S1到S2，S2到S3必须是bb，所以为B。故正确答案为：B -
第23题：
某确定的有限自动机（DFA）的状态转换图如下图所示（0 是初态，4 是终态），则该 DFA能识别（49）。
A.aaab
B.abab
C.bbba
D.abba答案：A解析：将选项分别带入判断。