下图所示的非确定有限自动机（So为初态，S3为终态）可识别字符串（ ） A.bbaa B.aabb C.abab D.baba

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

A.bbaa
B.aabb
C.abab
D.baba
相似考题

1.下图所示为两个有限自动机M1和M2(A是初态、C是终态)，(48)。A．M1和M2都是确定的有限自动机B．M1和M2都是不确定的有限自动机C．M1是确定的有限自动机，M2是不确定的有限自动机D．M1是不确定的有限自动机，M2是确定的有限自动机

2.下图所示的有限自动机中，s0是初始状态，s1为终止状态，该自动机不能识别( )。A．ababB．aaaaC．babbD．abba

3.某有限状态自动机的状态图如下图所示(状态0是初态，状态2是终态)，则该自动机不能识别______。A．ababB．aabbC．bbaaD．BbabA．B．C．D．

4.利用状态转换图识别字符串时，要从状态转换图的哪个状态出发来进行分析()。A、终态B、初态C、既非初态亦非终态D、任意状态

更多“下图所示的非确定有限自动机（So为初态，S3为终态）可识别字符串（ ） ”相关问题

  • 第1题：

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

    (48)

    A. (0|1)*01

    B．1*0*10*1

    C．1*(0)*01

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


    正确答案：A

  • 第2题：

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

    （48）

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

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

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

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


    正确答案：D

  • 第3题：

    ● 某有限状态自动机的状态图如下图所示（状态 0是初态，状态2是终态），则该自动机不能识别 （30） 。

    (30)

    A. abab

    B. aabb

    C. bbaa

    D. bbab


    正确答案：A

  • 第4题：

    某确定的有限自动机(DFA)的状态转换图如下图所示(A是初态，C是终态)，则该DFA能识别()。

    A.aabb

    B.abab

    C.baba

    D.Abba


    正确答案：B

  • 第5题：

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

    A. bbaa
    B.aabB.
    C.abab
    D. babA.

    答案：B
    解析：

  • 第6题：

    下图是一个有限自动机的状态转换图（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次或者无穷次。

  • 第7题：

    某非确定的有限自动机（NFA）的状态转换图如下图所示（q0既是初态也是终态），与该NFA等价的确定的有限自动机（DFA）是 （ ） 。



    答案：A
    解析：
    本题考查有限自动机这一知识点。容易看出，能被题中不确定的有限自动机接受的符号串有两种情形，一种是???表示的符号串，另一种是(ba)?符号串。在四个选项中，只有A选项的有限自动机能同时接受???和(ba)?这两种符号串，故本题选择A选项。

  • 第8题：

    下图是一个有限自动机的状态转换图（0为初态、3为终态),该自动机可识别字符串（ ）(即找出从初态到终态的路径上所标记的字符序列)。

    A.xxyy
    B.xyxy
    C.yyxx
    D.yxyx

    答案：A
    解析：
    选项依次带入，能从初态最后到终态的只有A。

  • 第9题：

    下图所示为一个不确定有限自动机（NFA）的状态转换图。该 NFA 识别的字符串集合可用正规式（ ）描述。


    A.ab*a
    B.（ab）*a
    C.a*ba
    D.a（ba）*

    答案：A
    解析：
    将四个选项分别带入可以得出答案。

  • 第10题：

    下图所示为一个不确定有限自动机（NFA）的状态转换图。该NFA可识别字符串（ ）。


    A.0110
    B.0101
    C.1100
    D.1010

    答案：A
    解析：
    由答案可知以0开始以0结尾，所以只有A符合。

  • 第11题：

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



    答案：C
    解析：
    NFA可以有000状态，因此排除A；NFA可以有010状态，可以排除BD。

  • 第12题：

    一个有限状态自动机中，有且仅有一个唯一的终态。


    正确答案:错误

  • 第13题：

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

    A.bbaa

    B.aabb

    C.abab

    D.baba


    正确答案：B

  • 第14题：

    ● 下图所示的有限自动机中，s0 是初始状态，s3 为终止状态，该自动机不能识别 （31）。

    （31）

    A.abab

    B.aaaa

    C.babb

    D.abba


    正确答案：A

  • 第15题：

    某确定的有限自动机 (DFA) 的状态转换图如下图所示 (A 是初态，D、E 是终态)，则该 DFA 能识别（ ）。

    A.00110B.10101C.11100D.11001


    正确答案：C

  • 第16题：

    以下关于下图所示有限自动机的叙述中．不正确的是 (49) 。

    A.该自动机识别的字符串中a不能连续出现

    B.该自动机识别的字符串中b不能连续出现

    C.该自动机识别的非空字符串必须以a结尾

    D.该自动机识别的字符串可以为空串


    正确答案：A
    本题考查程序语言基础知识。自动机识别字符串的过程是：从初态出发，根据字符串的当前字符实现状态转移。如果存在从初态到终态的状态转移路径与字符串中的各个字符相匹配，那么就说该自动机可以识别该字符串。题中所给自动机的初态和终态都是编号为1的状态，从其状态图可知，从状态1开始，识别出字符“a”时仍然转移到状态1，而识别出字符"b”时才离开状态1进入状态2，状态2仅对字符“a”有状态转移，且转回状态1。因此，该自动机识别的字符串仅包含a、b字符，但是字符"b”不能连续出现，连续出现“a”是可以的。

  • 第17题：

    某非确定的有限自动机（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结尾。

  • 第18题：

    下图是一个非确定有限自动机（NFA）的状态转换图，其中，S0为初态，S3为终态，该NFA可识别字符串（）（即找出从初态到终态的路径上所标记的字符序列）

    A.0101
    B.0011
    C.1100
    D.1010

    答案：A
    解析：
    判断一个字符串能否被指定的自动机识别,就是在该自动机的状态图中能否找到从开始状态到达终止状态的路径，且路径上的字符串等于需要识别的字符串。

  • 第19题：

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

    A.该自动机识别的字符串中a不能连续出现
    B.自动机识别的字符串中b不能连续出现
    C.自动机识别的非空字符串必须以a结尾
    D.自动机识别的字符串可以为空串

    答案：A
    解析：
    试题分析解析有误待修改图中a可代表两个步骤：状态1→1，状态2→1。如果两个a连续出现，则无法区分。

  • 第20题：

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




    答案：C
    解析：
    本题可以直接以实例方式排除错误选项。本题给出的NFA，能够识别字符串000,010等，以这两个字符串为例进行分析。与之等价的DFA，也必须能够识别这样的串。A选项不能识别000，B选项不能识别010，D选项不能识别010.只有C选项能够同时识别这2个串，因此本题选择C选项

  • 第21题：

    下图所示为一个不确定有限自动机（NFA）的状态转换图。该NFA不可识别字符串（ ）。

    A.0110
    B.01110
    C.00
    D.1010

    答案：D
    解析：
    将选项依次带入图中，注意该自动机可以识别空字符。

  • 第22题：

    某确定的有限自动机（DFA）的状态转换图如下图所示（0 是初态，4 是终态），则该 DFA能识别（49）。


    A.aaab
    B.abab
    C.bbba
    D.abba

    答案：A
    解析：
    将选项分别带入判断。

  • 第23题：

    一个确定有穷自动机有且只有一个终态。


    正确答案:错误

相关内容