● 对给定文法G=(VN,VT, P,S),VT={a,Λ,(,)},VN={S,T},S是开始符号, P: S→a|Λ|(T) T→T,S|S则(1)不

Question

● 对给定文法G=（VN，VT， P，S），VT={a，Λ，(，)}，VN={S，T}，S是开始符号，

P:

S→a|Λ|(T)

T→T,S|S

则（1）不是它的句子。该文法是（2）型文法。

（1）A. (a,(a,a)) B. (((a,a), Λ,(a)),a) C. ((a,a), Λ) D. ((a,a),(T))

（2）A．0型文法 B．1型文法 C．2型文法 D．正规文法

Answer 1

正确答案：D,C
根据句子的定义，若从文法G的开始符号S能推导出的符号串成为文法的一个句型，仅含终结符的句型成为一个句子。很显然，备选答案D中含有非非终结符T，所以它不是文法的句子。
该文法是递归可枚举的，所以文法是0型文法，又文法所有产生式的右边长度大于或等于产生式左边长度，所以文法是1型文法，由于该文法的每个产生式的左边均是非终结符，所以该文法是2型文法；由于文法的两个产生式即不是右线性，也不是左线性，所以该文法不是正规型文法。