文档介绍:考虑文法G[S],其产生式如下:
S→(L)|a
L→L,S|S
(1)试指出此文法的终结符号、非终结符号。
(2)给出下列各句子的分析树:
   ①(a,a)
   ②(a,(a,a))
   ③(a,((a,a),(a,a)))
(3)构造下列各句子的一个最左推导:
   ①(a,a)
   ②(a,(a,a))
   ③(a,((a,a),(a,a)))
(4)构造下列各句子的一个最右推导:
   ①(a,a)
   ②(a,(a,a))
   ③(a,((a,a),(a,a)))
(5)这个文法生成的语言是什么?
(a) 终结符号为:{(,),a,,,}
    非终结符号为:{S,L}
    开始符号为:S
(b) ①(a,a) ②(a,(a,a))
③(a,((a,a),(a,a)))
(c) ①(a,a)
    S (L) (L,S) (S,S) (a,S) (a,a)
    ②(a,(a,a))
    S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S))
      (a,(S,S)) (a,(a,S)) (a,(a,a))
    ③(a,((a,a),(a,a)))
    S (L) (L,S) (S,S) (a,S) (a,(L)) (a,(L,S))
      (a,(S,S)) (a,((L),S)) (a,((L,S),S)) (a,((S,S),S))
      (a,((a,S),S)) (a,((a,a),S)) (a,((a,a),(L)))
      (a,((a,a),(L,S))) (a,((a,a),(S,S))) (a,((a,a),(a,S)))
      (a,((a,a),(a,a)))
(d) ①(a,a)
    S (L) (L,S) (L,a) (S,a) (a,a)
    ②(a,(a,a))
    S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,a))
      (L,(S,a)) (L,(a,a)) (S,(a,a)) (a,(a,a))
    ③(a,((a,a),(a,a)))
    S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,(L)))
      (L,(L,(L,S))) (L,(L,(L,a))) (L,(L,(S,a)))
      (L,(L,(a,a))) (L,(S,(a,a))) (L,((L),(a,a)))
      (L,((L,S),(a,a))) (L,((L,a),(a,a))) (L,((S,a),(a,a)))
      (L,((a,a),(a,a))) (S,((a,a),(a,a))) (a,((a,a),(a,a)))
(e) L(G[S]) = (α1,α2,...,αn)或a
    其中αi(1≤i≤n),即L(G[S])是一个以a为原子的纯表,但不包括空表。
考虑文法G[S]
S→aSbS| S->aSbS | bSaS |ε
(1)试说明此文法是二义性的。可以从对于句子aba