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