违法和不良信息举报 联系客服
免费注册 登录

以下关于下图所示有限自动机的叙述中，不正确的是 （ ） 。

题目
以下关于下图所示有限自动机的叙述中，不正确的是 （ ） 。

A.该自动机识别的字符串中a不能连续出现
B.自动机识别的字符串中b不能连续出现
C.自动机识别的非空字符串必须以a结尾
D.自动机识别的字符串可以为空串
参考答案和解析
答案：A
解析：
试题分析解析有误待修改图中a可代表两个步骤：状态1→1，状态2→1。如果两个a连续出现，则无法区分。
如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

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

第2题：

某有限状态自动机的状态图如下图所示(状态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。

第3题：

下图所示的有限自动机中，0是初始状态，3是终止状态，该自动机可以识别(22)。

A．abab

B．aaaa

C．bbbb

D．abba


正确答案：B
解析：A选项中到达状态3后输入a再次回到状态3，但输入b后无法被识别。c选项中经过的状态为0→1→2→3，在状态3时输入b无法被识别。D选项中在第二次输入b后即不能被识别。

第4题：

下图所示的非确定有限自动机（S0为初态，S3为终态）可识别字符串（）。

A.bbaa

B.aabb

C.abab

D.baba


正确答案：B

第5题：

● 下图所示有限自动机的特点是 （48） 。

（48）

A. 识别的0、1串是以0开头且以1结尾

B. 识别的0、1串中1的数目为偶数

C. 识别的0、1串中0后面必须是1

D. 识别的0、1串中1不能连续出现


正确答案：D

第6题：

下图所示的有限自动机中，s0是初始状态，s1为终止状态，该自动机不能识别( )。

A．abab

B．aaaa

C．babb

D．abba


正确答案：A
解析：要判断一个字符串能否被指定的自动机识别，就看在该自动机的状态图中能否找到一条从开始状态到终止状态的路径，且路径上的字符串等于要识别的字符串。对于字符串“abab”，识别路径为s0→s1→s2→s1→s2，字符串结束时的状态不是终止状态，所以该自动机不能识别“abab”。字符串“aaaa”的识别路径为s0→s1→s3→s3→s3，字符串“babb”的识别路径为s0→s2→s1→s2→s3，字符串“abba”的识别路径为s0→sl→s2→s3→s3，它们结束时的状态都是终止状态，所以都能被自动机识别。

第7题：

●下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机识别的语言可用正规式(48)表示。

(48)

A. (0|1)*01

B．1*0*10*1

C．1*(0)*01

D.1*(0|10)*1*


正确答案：A

第8题：

下图所示为两个有限自动机M1和M2(A是初态、C是终态)，(48)。

A．M1和M2都是确定的有限自动机

B．M1和M2都是不确定的有限自动机

C．M1是确定的有限自动机，M2是不确定的有限自动机

D．M1是不确定的有限自动机，M2是确定的有限自动机


正确答案：D
解析：在计算理论中，非确定有限状态自动机或非确定有限自动机(NFA)是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机(DFA)，它的下一个可能状态是唯一确定的。图中，M1的状态A中当输入0时，既可以转为状态A也可以转为状态B，M2中的每个状态在一种输入的情况下，下一个状态始终是确定的。所以，M1为不确定的，M2为确定的。

第9题：

● 某确定性有限自动机（DFA）的状态转换图如下图所示，令 d=0|1|2|...|9，则以下字符串中，能被该DFA 接受的是 （49） 。

（49）

A. 3857

B. 1.2E+5

C. -123.67

D. 0.576E10


正确答案：C

第10题：

● 下图所示为两个有限自动机M1和M2（A是初态、C是终态）， （48） 。

（48）

A. M1和M2都是确定的有限自动机

B. M1和M2都是不确定的有限自动机

C. M1是确定的有限自动机，M2是不确定的有限自动机

D. M1是不确定的有限自动机，M2是确定的有限自动机


正确答案：D

更多相关问题
相关内容