22、有穷自动机有了非确定性, 增加了它识别语言的能力。

题目

22、有穷自动机有了非确定性, 增加了它识别语言的能力。

相似考题

1.●根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与 (28) 等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价 (29) 。从文法描述语言的能力来说， (30) 最强， (31) 最弱，由4类文法的定义可知： (32) 必是2型文法。(28) A．线性有限自动机B．非确定的下推自动机C．图灵机D．有限自动机(29) A．确定的有限自动机B．图灵机C．非确定的下推自动机D．非确定的有限自动机(30) A．1型文法B．2型文法C．3型文法D．0型文法(31) A．3型文法B．2型文法C．0型文法D．1型文法(32) A．1型文法B．0型文法C．3型文法D．2型文法

2.下图所示的有限自动机中，0是初始状态，3是终止状态，该自动机可以识别(22)。A．ababB．aaaaC．bbbbD．abba

3.根据乔姆斯基20世纪50年代建立的形式语言的理论体系，语言的文法被分为四种类型，即：O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(67)。从文法描述语言的能力来说，(68)最强，(69)最弱，由四类文法的定义可知：(70)必是2型文法。(40)A．确定的有限自动机B．图灵机C．非确定的下推自动机D．非确定的有限自动机E．有限自动机

4.●文法G=({E}，{+，*，(，)，a}，P，E)，其中P由下列产生式组成E->E+E｜E*E｜(E)｜a。它生成由a，+，*，(，)组成的算术表达式，该文法在乔姆斯基分层中属于 (33) 型文法，其对应的自动机是 (34) ，如产生句子a*a+a，它的派生树是 (35) ，且最左派生由 (36) 种，该文法是 (37) 。(33) A．0B．1C．2D．3(34) A．下推自动机B．线性有界自动机C．图灵机D．有穷状态自动机(35) A．二叉树B．完全有界自动机C．三叉树D．四叉树(36) A．0B．1C．2D．3(37) A．非二义性B．二义性C．单一性D．多义性

更多“22、有穷自动机有了非确定性, 增加了它识别语言的能力。”相关问题

  • 第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所识别正规集的真子集


    正确答案：B

  • 第2题：

    下推自动机识别的语言是()

    A、0型语言

    B、1型语言

    C、2型语言

    D、3型语言


    参考答案：C

  • 第3题：

    是否存在能被确定的有穷自动机识别，但不能用正则表达式表示的语言()。

    A、存在

    B、不存在

    C、可能存在

    D、无法判定是否存在


    参考答案：B

  • 第4题：

    ()这样一些语言,它们能被确定的有穷自动机识别,但不能用正则表达式表示。

    A.存在

    B.不存在

    C.无法判定是否存在

    D.以上答案都不对


    正确答案：B

  • 第5题：

    算法的重要特征有()

    A、有穷性

    B、确定性

    C、可行性

    D、有输出


    参考答案：ABCD

  • 第6题：

    图7-17是一有穷自动机的状态转换图，该自动机所识别语言的特点是(1)，等价的正规式为(2)。

    A．由符号a、b构成且包含偶数个a的串

    B．由符号a、b构成且开头和结尾符号都为a的串

    C．由符号a、b构成的任意串

    D．由符号a、b构成且b的前后必须为a的串


    正确答案：B

  • 第7题：

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

    （22）

    A. abab

    B. aaaa

    C. bbbb

    D. abba


    正确答案：B

  • 第8题：

    设有穷自动机的状态转换图如下图，该自动机识别的语言是(29)。

    A．∑={0，1)上的所有符号串的集合，但不包含空符号串

    B．空符号串集合

    C．∑={0，1)上的所有符号串的集合，包含空符号串

    D．空集合


    正确答案：D
    解析：因为从有穷自动机的开始状态A出发，无法到达终止状态B，所以该有穷自动机不能接受任何符号串，即该有穷自动机识别的语言为空集合。

  • 第9题：

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

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

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

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

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


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

  • 第10题：

    下面哪个不是单词的描述工具？（）

    • A、正规式
    • B、有穷自动机
    • C、下推自动机
    • D、正规文法

    正确答案:C

  • 第11题：

    （）这样一些语言，它们能被确定的有穷自动机识别，但不能用正规表达式表示。

    • A、存在
    • B、不存在
    • C、无法判定是否存在

    正确答案:B

  • 第12题：

    单选题
    下面哪个不是单词的描述工具？（）
    A

    正规式

    B

    有穷自动机

    C

    下推自动机

    D

    正规文法


    正确答案： D
    解析： 暂无解析

  • 第13题：

    Chomsky定义的四种形式语言文法中，2型语言可由()识别。

    A、短语结构文法

    B、前后文无关文法

    C、前后文有关文法

    D、正规文法

    E、图灵机

    F、有限自动机

    G、下推自动机


    参考答案：G

  • 第14题：

    有穷自动机能够识别上下文无关语言。()


    参考答案：错误

  • 第15题：

    计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、()等5个特性。

    A、可执行性、有穷性和可扩充性

    B、可执行性、有穷性和确定性

    C、确定性、无穷性和稳定性

    D、易读性、稳定性和确定性


    参考答案：B

  • 第16题：

    根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(28)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(29)。从文法描述语言的能力来说，(30)最强，(31)最弱，由4类文法的定义可知：(32)必是2型文法。

    A．线性有限自动机

    B．非确定的下推自动机

    C．图灵机

    D．有限自动机


    正确答案：B

  • 第17题：

    算法具有5个特性:()输入和输出。

    A.稳定性、确定性、可行性

    B.有穷性、确定性、可行性

    C.有穷性、安全性、可行性

    D.有穷性、确定性、可移植性


    参考答案：B

  • 第18题：

    根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，文法被分为4种类型，即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(1)等价，所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的有穷自动机必存在一个与之等价的(2)。从文法描述语言的能力来说，(3)最强，(4)最弱，由4类文法的定义可知(5)必是2型文法。

    A．确定的有穷自动机

    B．图灵机

    C．非确定的下推自动机

    D．非确定的有穷自动机

    E．有穷自动机


    正确答案：C

  • 第19题：

    计算机算法是指解决问题的有限运算序列，它具备______和足够的信息。

    A．可行性、可移植性、可扩充性

    B．易读性、稳定性、安全性

    C．确定性、有穷性、稳定性

    D．可行性、确定性、有穷性


    正确答案：D
    解析： 算法的基本特征是可行性、确定性、有穷性和拥有足够的信息。

  • 第20题：

    对高级语言源程序进行编译的过程中,有穷自动机(NFA或DFA)是进行(49)的适当工具。A.词法分析SXB

    对高级语言源程序进行编译的过程中，有穷自动机（NFA或DFA）是进行（49）的适当工具。

    A.词法分析

    B.语法分析

    C.语义分析

    D.出错处理


    正确答案：A
    编译程序的功能是从源代码（通常为高级语言）到能直接被计算机或虚拟机执行的目标代码（汇编语言或机器语言）的翻译过程。工作过程分为6个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。各个阶段逻辑上可以分为前端和后端。前端主要负责解析输入的源代码，由语法分析器和语意分析器协同工作。语法分析器负责把源代码中的‘单词’找出来，语意分析器把这些分散的单词按预先定义好的语法组装成有意义的表达式、语句、函数等等。前端还负责语义的检查，例如检测参与运算的变量是否是同一类型的，简单的错误处理。最终的结果常常是一个抽象的语法树，这样后端可以在此基础上进一步优化处理。后端编译器后端主要负责分析，优化中间代码以及生成机器代码。

  • 第21题：

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

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

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

  • 第22题：

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


    正确答案:错误

  • 第23题：

    判断题
    一个确定有穷自动机有且只有一个终态。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第24题：

    单选题
    （）这样一些语言，它们能被确定的有穷自动机识别，但不能用正规表达式表示。
    A

    存在

    B

    不存在

    C

    无法判定是否存在


    正确答案： C
    解析： 暂无解析

相关内容