设有文法G［W］：W→A0A→A0｜W1｜0，改写文法消除左递归

设有文法： W→AO A→A0|W1|0 将它改写后消除左递归后的文法是(27)。

A．W→A0 A→0A' A'→0A'|01A'|ε

B．W→A0 A→A0 |A01| 0

C．W→A0 A→0A' A→0A'|01A'

D．以上均不对

设有关系模式W(C,P,S,C,T,R)，其中各属性的含义是：C——课程，p——教师，S——学生，G——成绩，T——时间，R——教室，根据语义有如下数据依赖集：

D={C→4P，(S，C)→G，(T,R)→C，(T,P)→R，(T,S)→R}

关系模式w的一个码(关键字)是(39)，W的规范化程度最高达到(40)。若将关系模式W分解为3个关系模式W1(C,P)、W2(S,C,G)、W3(S,T,R,C)。则W1的规范化程度最高达到(41)，W2的规范化程序最高达到(42)，W3的规范化程序最高达到(43)。

A．(S，C)

B．(T，R)

C．(T，P)

D．(T，S)

A、1NF

B、2NF

C、3NF

D、BCNF

●设有关系模式W(C，P，S，G，T，R)，其中各属性的含义是：C--课程，P--教师，S--学生，G--成绩，T--时间，R--教室，根据语义有如下数据依赖集：

D={C→P，(S，C)→G，(T，R)→C，(T，P)→R，(T，S)→R}

关系模式W的一个码(关键字)是 (39) ，W的规范化程度最高达到 (40) 。若将关系模式W分解为3个关系模式W1(C，P)、W2(S，C，G)、W3(S，T，R，C)。则W1的规范化程度最高达到 (41) ，W2的规范化程序最高达到 (42) ，W3的规范化程序最高达到 (43) 。

(39) A．(S，C)

B．(T，R)

C．(T，P)

D．(T，S)

(40)～(43) A．1NF

B．2NF

C．3NF

D．4NF

A.W1（工号，姓名），W2（工种，定额）

B.W1（工号，工种，定额）W2（工号，姓名）

C.W1（工号，姓名，工种）w2（工种，定额）

D.以上都不对

A.W1(编号，姓名)W2(工种，基本工资)

B.W1(编号，职称，基本工资)W2(编号，姓名)

C.W1(编号，姓名，职称)W2(编号，基本工资)

D.以上都不对

A.W1(工号，姓名)，W2(工种，定额)

B.W1(工号，定额)，W2(姓名，工种)

C.W1(工号，姓名，工种)，W2(工种，定额)

D.W1(工号，工种，定额)，W2(工号，姓名)

1. 文法G＝({A,B,S},{a,b,c},P,S), 其中P 为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 2. 文法G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？ 3. 考虑下面上下文无关文法： S→SS*|SS+|a (1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 (2)G[S]的语言是什么？ 4. 给出生成下述语言的二型文法： (1) {anbn | n ＞=0 } (2) { ambn | m≥n ≥0 } (3) {uawb | u,w ∈{a,b}*∧|u|=|w| } (4) { anbm | n≥2m ≥0 } (5) { anbm | n ≥ 0, m ≥ 0,3n≥m≥2n } (6) {wwR|w∈{a,b}*，wR 表示w的逆} (7) {uvwvR|u,v,w∈{a,b}+=1 } 5. 给出生成下述语言的三型文法： (1) {an | n ＞=0 } (2) { anbm | n,m＞=1 } (3) {anbmck | n,m,k＞=0 }

A.xx*|yy*|zz*

B.(xx*|yy*)zz*

C.xx*(yy*|zz*)

D.(xx|yy)*zz*

A.1型(上下文有关)文法

B.2型(上下文无关)文法

C.定义标识符的3型(正规)文法

D.0型文法