已知一不确定的有限自动机(NFA)如图6-6所示，采用子集法将其确定化为DFA的过程如表6-1所示。状态集T1中不包括编号为(58)的状态；状态集T2中的成员有(59)；状态集乃等于(60)；该自动机所识别的语言可以用正则式(61)表示。A．2B．4C．3D．5

题目

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

状态集T1中不包括编号为(58)的状态；状态集T2中的成员有(59)；状态集乃等于(60)；该自动机所识别的语言可以用正则式(61)表示。

A．2

B．4

C．3

D．5

相似考题

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

2.已知一个NFA M图如下所示，采用子集构造法将其确定化为DFA的过程如下表所示。表中的状态集合T是(27)。A．{1，2}B．{3，4，5}C．{4，5}D．{6}

3.某一非确定性有限自动机(NFA)的状态转换图如图6-1所示，该NFA等价的正规式是(1)，与该NFA等价的DFA是(2)。A．0*|(0|1)0B．(0|10)*C．0*((0|1)0)*D．0*(10)*

4.已知一不确定的有限自动机(NFA)如图2-8所示，采用子集法将其确定化为DFA的过程如表2-1所示。状态集T1中不包括编号为(23)的状态；状态集T2中的成员有(24)：状态集T3等于(25)；该自动机所识别的语言可以用正规式(26)表示。A．2B．4C．3D．5

参考答案和解析
正确答案：A
更多“ 已知一不确定的有限自动机(NFA)如图6-6所示，采用子集法将其确定化为DFA的过程如表6-1所示。状态集T1中不包括编号为(58)的状态；状态集T2中的成员有(59)；状态集乃等于(60)；该自动机所识别的语言”相关问题

  • 第1题：

    有限自动机(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。

  • 第2题：

    某一非确定性有限自动机（NFA）的状态转换图如下图所示，与该NFA等价的正规式是（ ），与该NFA等价的DFA是（请作答此空）。




    答案：A
    解析：

  • 第3题：

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



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

  • 第4题：

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



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

  • 第5题：

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




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

相关内容