●根据乔姆斯基于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型文法

相关问题推荐

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

  A、正规式

  B、有穷自动机

  C、下推自动机

  D、正规文法

  查看答案

• 下图所示的有限自动机中，s0是初始状态，s1为终止状态，该自动机不能识别()。

  A．abab

  B．aaaa

  C．babb

  D．abba

  查看答案

• 一个有限自动机识别的语言是一个无限集合，则该有限自动机的状态图一定含有回路。（)

  此题为判断题（对，错)。

  查看答案

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

  查看答案
• 图灵在密码方面取得的成就_______。他发明了“图灵机”。虽然这个机器当时是为战争服务的，不过，在人工智能的发展历史中，却是_______的一个事件。
  A.可望而不可即，并天辟地
  B.可望而不可及，开天辟地
  C.可望而不可及，开天劈地
  D.可望而不可即，开天劈地

  查看答案