形式语言与文法.ppt

第2章练习题一，单选题1.给定文法：A→bA|cc,下面的符号串为该文法句子的是（）。①cc②bcbcc③bccbcc④bbbccA.①④B.①②③C.①③D.②③④2.文法G[Z]和语言L（G[Z]）存在如下关系（）。A.一一对应：一个文法对应唯一的语言；并且反过来，一个语言对应唯一的文法。B.一个语言对应唯一的文法，反之则不然。C.一个文法对应唯一的语言，反之则不然。D.若G为非二义性文法，则C是正确的；若G为二义性文法，则一个文法不对应唯一的语言。

3.有文法G[E]：E→－EE，E→－E，E→a|b|c则文法的句子－－a－bc的所有可能的语法树有（）棵。A.1B.2C.4D.34.有文法G[S]，如果Sx，(x∈V)，则x是（）。A.句型B.句子C.A和BD.非A和B二.构造一个上下文无关文法G，使得：L(G)={ab|m0}*T2mm

已知文法G[E]：E→ET+|TT→TF*|FF→FP↑|PP→(E)|i有句型TF*PP↑+，问此句型的短语，简单短语和句柄是什么？（画语法树说明）

S→SS|(S)|()。请用语法树证明文法G[s]是二义性的，G[s]：01A→aAb|abB→Bc|ε则，L(G[Z])＝？已知文法G[Z]：Z→AB02