文档介绍：+、*和↑代表加,乘和乘幂,按如下的非标准优先级和结合性质的约定,计算1+1*2↑2*1↑2的值:优先顺序(从高至低)为+,*和↑,同级优先采用左结合。优先顺序为↑,+,*,同级优先采用右结合。解:(1)1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16(2)1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=→D|NDD→0|1|2|3|4|5|6|7|8|9G6的语言L(G6)是什么?给出句子0127、34和568的最左推导和最右推导。解:(1)L(G6)={a|a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9}}(2)N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127N=>ND=>DD=>3D=>34N=>ND=>N4=>D4=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568N=>ND=>N8=>ND8=>N68=>D68=>,使其语言是奇数集,且每个奇数不以0开头。解:A→SN,S→+|-|∑,N→D|MDD→1|3|5|7|9,M→MB|1|2|3|4|5|6|7|8|9B→0|1|2|3|4|5|6|7|8|:最左推导:最右推导:语法树:/*************************************************/:S→iSeS|iS|I解:因为iiiiei有两种最左推导,所以此文法是二义的。:S→SS|(S)|()解:S→ST|T,T→(S)|()={anbnci|n≥1,i≥0}L2={|n≥1,i≥0}L3={anbnambm|n,m≥0}L4={1n0m1m0n|n,m≥0}解:(1)S→AB|AA→aAb|abB→c|cB(2)S→AB|BA→a|aAB→bBc|bc(3)S→AB|A|B|∑A→aAb|abB→aBb|abS→1S0|0A1A→0A1| 1(0|1)*101 1(1010*|1(010)*1)*0 0*10*10*10* (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*解答:(1)1(0|1)*101I I0 I1{X} Ф{A,B,C} {A,B,C} {B,C} {B,C,D} {B,C} {B,C} {B,C,D} {B,C,D} {B,C,E} {B,C,D}{B,C,E} {B,C} {B,C,D,y}{B,C,D,y} {B,C,E} {B,C,D}S 0 1A BB C DC C DD E DE C FF E D(2)1(1010*|1(010)*1)*0I I0 I1Ф{A,B,C}{A,B,C} {y} {D,H,I,L}{y} ФФ{D,H,I,L} {E,J} {B,C}{E,J} Ф{B,C,F,G,K}{B,C} {y} {D,H,I,L}{B,C,F,G,K} {B,C,G,I,L,y} {D,H,I,L}{B,C,G,I,L,y} {B,C,G,J,y} {B,C,D,H,I,L}{B,C,G,J,y} {B,C,G,y} {D,H,I,L}{D,H,I,K,L} {E,I,J,L} {B,C}{E,J,y} Ф{B,C,F,G,K}{E,I,J,L} {J} {B,C,F,G,K}{J} Ф{K}{K} {I,L} Ф{I,L} {J} {B,C},要求符号串中的字母按照字典序排列。(7)不包含子串abb的由a和b组成的符号串的全体。解答:(0|1)*01(1|2|…|9)(0|1|2|…|9)*(0|5)|0|50*1(0*10*10*)*A*B*…Z*(7)b*(a|ab)*。(1){0,1}上的含有子串010的所有串。(2){0,1}上不含子串010的所有串。解答:(1)(0|1)*010(0|1)*(2)1*(0|1*|1)*1*(a)和(b)分别确定化和最少化。解:1确定化ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}__令A={0}B={0,1}C={1}则状态转换图为:2最少化首先,所有状态可分为终态集{AB}非终态集{C}其次,考察{AB},由于{AB}由a到{B},由b到{C},所以不可分,令A={AB}则最少化后的状态转换图