●文法G=({E},{＋,*,(,),a},P,E),其中P由下列产生式组成E－>E＋E|E*E|(E)|a。它生成由a,＋,*,(,)组

Question

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

Answer 1

正确答案：C,A,C,C,B
【解析】乔姆斯基定义了4种文法类型，他们之间的差别是按文法G=(V_N，V_T，P，S)t辛P所允许的产生式的形式加以区分的。如果P中的每个产生式形式如A->P，其中A为非终结符，P为P*，则称此文法为2型文法或上下文无关文法。对应的语言称为上下文无关语言，对用的自动机称为下推自动机。题中的文法属于1型对应的下推自动机。

                                                                                                      图3派生树
产生句子a*a+a的派生树有两棵，如图3所示：
这是三叉树，最左派生有两种，它们是
E=>E+E=>E*E+E=>a*E+E=>a*a+E=>a*a+a
E=>E*E=>a*E=>a*E+E=>a*a+E=>a*a+a
因此，该文法是二义的。