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

A．线性有限自动机

B．非确定的下推自动机

C．图灵机

D．有限自动机

相关问题推荐

• 一般把上下文语境分为环境上下文，场所上下文，文字上下文。

  A、对

  B、错

  查看答案

• ●文法G=({E}，{+，*，(，)，a}，P，E)，其中P由下列产生式组成E->E+E｜E*E｜(E)｜a。它生成由a，+，*，(，)组成的算术表达式，该文法在乔姆斯基分层中属于(33)型文法，其对应的自动机是(34)，如产生句子a*a+a，它的派生树是(35)，且最左派生由(36)种，该文法是(37)。

  (33)A．0

  B．1

  C．2

  D．3

  (34)A．下推自动机

  B．线性有界自动机

  C．图灵机

  D．有穷状态自动机

  (35)A．二叉树

  B．完全有界自动机

  C．三叉树

  D．四叉树

  (36)A．0

  B．1

  C．2

  D．3

  (37)A．非二义性

  B．二义性

  C．单一性

  D．多义性

  查看答案

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

  A、短语结构文法

  B、前后文无关文法

  C、前后文有关文法

  D、正规文法

  E、图灵机

  F、有限自动机

  G、下推自动机

  查看答案

• 将识别各类单词的有限自动机合并后得到的有限自动机_______。
  A．可能是NFA也可能是DFA
  B．一定是DFA
  C．一定是NFA
  D．是最小的DFA

  查看答案