_____A．图灵机B．下推自动机C．其他自动机D．有限状态自动机A．B．C．D．

题目

_____

A．图灵机

B．下推自动机

C．其他自动机

D．有限状态自动机

A．

B．

C．

D．

相似考题

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.●文法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．多义性

3.若将有限状态自动机(DFA)识别的0、1符号串看做二进制数，则自动机(27)识别的是能被十进制数3整除的正整数。A．B．C．D．

4.●文法G=(VT，VN，P，S)的类型由G中的 (32) 决定。若G0=({a,b}，{S，X，Y}，P，S)，P中的产生式及其序号如下：1：S→XaaY2：X→YYlb3：Y→XbXla则G0为 (33) 型文法，对应于 (34) ，由G0推导出句子aaaaa和baabbb时，所用产生式序号组成的序列分别为 (35) 和 (36) 。(32) A．VTB．VNC．PD．S(33) A．0B．1C．2D．3(34) A．图灵机B．下推自动机C．有限状态自动机D．其他自动机(35),(36) A．13133B．12312C．12322D．12333

更多“_____A.图灵机B.下推自动机C.其他自动机D.有限状态自动机A.B.C.D. ”相关问题

  • 第1题：

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

    (40)

    A．确定的有限自动机

    B．图灵机

    C．非确定的下推自动机

    D．非确定的有限自动机

    E．有限自动机


    正确答案：C

  • 第2题：

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

    A．线性有限自动机

    B．非确定的下推自动机

    C．图灵机

    D．有限自动机


    正确答案：B

  • 第3题：

    3、识别上下文无关语言的自动机是（)。

    A．下推自动机

    B．NFA

    C．DFA

    D．图灵机


    A

  • 第4题：

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

    A、短语结构文法

    B、前后文无关文法

    C、前后文有关文法

    D、正规文法

    E、图灵机

    F、有限自动机

    G、下推自动机


    参考答案：G

  • 第5题：

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

    A．确定的有限自动机

    B．图灵机

    C．非确定的下推自动机

    D．非确定的有限自动机

    E．有限自动机


    正确答案：C
    解析：乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。0型文法也称短语文法，0型文法的能力相当于图灵机(Turing)，或者说任何0型语言都是递归可枚举的。1型文法也称上下文有关方法，其能力相当于线形界限自动机。对非终结符进行替换时不必考虑上下文，并且一般不允许替换成空串ε。2型文法也称上下文无关文法，其能力相当于非确定的下推自动机。3型文法也称右线性文法，由于这种文法等价于正规式，所以也称正规文法。3型文法的能力相当于有限自动机。从文法描述语言的能力来说，0型文法最强，3型文法最弱。语言的文法可以表示成一个四元组(VT,VN,S,P)。由3型文法的定义：一个文法G式3型文法，如果G是二型文法，并且G的每个产生式A→αB或A→α，其中O∈V*T，A，B∈VN，可知3型文法必是2型文法。

相关内容