:
2.1 考虑文法G[S],其产生式如下S|S
，→(L)|a L→LS 试指出此文法的终结符号、非终结符号。(1)
终结符号为：{S,L} 非终结符号为：S
,,} {(,),a,
开始符号为： (2)给出下列各句子的分析树：③②(a,(a,a)) (a,((a,a),(a,a))) (a,a) ①
(3)构造下列各句子的一个最左推导：
① (a,a)
(L) (L,S) (S,S) S (a,S) (a,a)
② (a,(a,a))
(L,S) (S,S) (a,S) (a,(L) S (a,(L,S)) (L)
(a,(S,S)) (a,(a,S)) (a,(a,a))
③ (a,((a,a),(a,a)))
(L,S) (S,S) (a,S) (a,(L)) (a,(L,S)) S (L)
(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),(a,S))) (a,((a,a),(L,S))) (a,((a,a),(S,S)))
(a,((a,a),(a,a)))
(4)构造下列各句子的一个最右推导：(a,a)
①(a,a) (L) (L,a) (L,S) S (S,a)
a))
(a,(a，②(L,(L,a)) (L,S) (L,(L,S)) S (L,(L)) (L)
(a,(a,a) (L,(S,a)) (S,(a,a)) (L,(a,a))
a))
(a③(a，((a，a)，，(L,(L,(L))) (L,(L)) S (L,S) (L) (L,(L,S))
(L,(L,(S,a))) (L,(L,(L,S))) (L,(L,(L,a)))
(L,((L),(a,a)))
(L,(L,(a,a))) (L,(S,(a,a)))
(L,((S,a),(a,a))) (L,((L,S),(a,a))) (L,((L,a),(a,a)))
(a,((a,a),(a,a))) (L,((a,a),(a,a))) (S,((a,a),(a,a)))
(5)这个文法生成的语言是什么？...a
,α,,α)或L(G[S]) = (αn12 n)，即L(G[S])是一个以a为原子的纯表，但不包括空表。≤其中α(1≤i i2.2 考虑文法G[S] S→aSbS|bSaS|ε (1)试说明此文法是二义性的。可以从对于句子abab有两个不同的最左推导来说明。abab
S aSbS abaSbS abS ababS
abab S aSbS abSaSbS abaSbS ababS
所以此文法是二义性的。 (2)对于句子abab构造两个不同的最右推导。
abab aSbS aSbaSbS aSbaSb S aSbab
abab aSbS aSb abSaSb abSab S
构造两棵不同的分析树。(3)对于句子abab)
二 ( (一)
此文法所产生的语言是什么？(4) 组成的字符串。和ba此文法产生的语言是：所有a的个数与b的个数相等的由 L,S|S
→→ (L)|a L 2.4 已知文法G[S]的产生式如下：S
最右推导 B ，L(G[S])的句子，这个句子的最左推导是是属于L(G[S])的句子是 A ，(a,a)。 D ，句柄是 E C 是，分析树是 (L,a)
④ a,a ③ (L) ②：①A a
(a,a) (L,a) (S,a) (L) ：①B,C S (L,S)
(a,a)
(S,S) (L) ② S (L,S) (S,a)
(a,a)
(L,S) ③(a,S) S (S,S) (L)
：D
a
④③ (a) ：①E (a,a) ② a,a
：④ D：② E解答： A：① B：③ C：①3.1有限状态自动机可用五元组（V，Q，δ，q，Q）来描述,设有一有限状态自动机M的定义如下：f0T V={0,1}，Q={q,q,q}，Q={q}，δ的定义为：21T0f2δ（q，0）=q δ（q，0）=q 2110）=qq，0 =q δ（，δ（q1）2222M是一个 A 有限状态自动机，它所对应的状态转换图为 B ,它所能接受的语言可以用正则表达式表示为 C 。其含义为 D 。
A: ①歧义的②非歧义的③确定的④非确定的
B:
④0(0|1)(0|1) C：①(0|1) ②00(0|1) ③所组成的符号串的集合；和1：①由
****0 00
D0 0②以0为头符号和尾符号、由和1所组成的符号串的集合；
结束的，由③以两个 001和所组成的符号串的集合；
所组成的符号串的集合。和1 ④以两个0开始的，由0 D:④ B:② C:②③答案 A:
（） (1)有穷自动机接受的语言是正则语言。3.2
（）|r也是。若r和r是Σ上的正规式，则r(2)21124个。，则NFA，并且L(M)＝{x,y,z}M的状态数至少为(3)设M是一个** (a|b)。{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为
b(4)令Σ＝。（）对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)(5) ，反之亦然。（）对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')(6)T (5) (4) F (2) 答案 (1) T T (3) F
描述下列各正规表达式所表示的语言。 3.3*0
0(0|1)(1)
ε*0(0|1)(0|1)
** |0)1)(2) ((
(3) (0|1)**** 1010(4) 010*
}{0,1}|α∈和结尾的，由01组成的所有符号
***)(01|10)(00|11)(5) (00|11)((01|10)(00|11)*
串(2) {α答案 (1) 以0开头并且以0 组成的所有符号串。0和1即由位为0。由0和1组成的符号串，且从右边开始数第3(3)
3α且中含有α∈{0,1}+，1个的由0和1 {组成的所有符号串。α|(4) 含31 }
个*和10的数目为偶数。}
中含α{|α∈{0,1},α(5)
4.10 已知文法G[S]，其产生式如下：S→(L)|a L→L,S|S
文法G[S]的算符优先关系由下表给出。建立与下表相应的算符优先函数并用算符优先分析法分
析句子(a,(a,a))。
