●文法G=(VT，VN，P，S)的类型由G中的 (32) 决定。若G0=({a,b}，{S，X，Y}，P，S)，P中的产生式及其序号如下：

1：S→XaaY

2：X→YYlb

3：Y→XbXla

则G0为 (33) 型文法，对应于 (34) ，由G0推导出句子aaaaa和baabbb时，所用产生式序号组成的序列分别为 (35) 和 (36) 。

(32) A．VT

B．VN

C．P

D．S

(33) A．0

B．1

C．2

D．3

(34) A．图灵机

B．下推自动机

C．有限状态自动机

D．其他自动机

(35),(36) A．13133

B．12312

C．12322

D．12333

相关问题推荐

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

  A．abab

  B．aaaa

  C．babb

  D．abba

  查看答案

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

  A、短语结构文法

  B、前后文无关文法

  C、前后文有关文法

  D、正规文法

  E、图灵机

  F、有限自动机

  G、下推自动机

  查看答案

• 以下关于语言L={anbn|n>=1}的叙述中，正确的是（）。

  
  A.可用正规式“aa*bb*”描述，但不能通过有限自动机识别B.可用正规式“ambm”表示，但可用有限自动机识别C.不能用正规式表示，但可用有限自动机识别D.既不能用正规式表示，也不能通过有限自动机识别

  查看答案

• 某一确定有限自动机(DFA)的状态转换图如下，与该自动机等价的正规表达式是(28)，图中(29)是可以合并的状态。

  (42)

  A．(a|ba)*bb(a*b*)*

  B．(a|ba)*bba*|b*

  C．(a*|b*)bb(a|b)*

  D．(a|b*)*bb(a*|b*)

  查看答案

• 1937年，图灵在发表的论文（）中，首次提出图灵机的概念。

  A、《左右周期性的等价》

  B、《论可计算数及其在判定问题中的应用》

  C、《可计算性与λ可定义性》

  D、《论高斯误差函数》

  查看答案