对给定文法G=(VN VT P S) VT={a Λ ( )} VN={S T} S是开始符号 P: S→a|Λ|(T) T→T S|S则(1)不
文法,符号,句子
已帮助 人
对给定文法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.正规文法
-
参考答案:D,C根据句子的定义,若从文法G的开始符号S能推导出的符号串成为文法的一个句型,仅含终结符的句型成为一个句子。很显然,备选答案D中含有非非终结符T,所以它不是文法的句子。该文法是递归可枚举的,所以文法是0型文法,又文法所有产生式的右边长度大于或等于产生式左边长度,所以文法是1型文法,由于该文法的每个产生式的左边均是非终结符,所以该文法是2型文法;由于文法的两个产生式即不是右线性,也不是左线性,所以该文法不是正规型文法。
