计算理论习题答案CHAP7new(共8页).doc

7.3a.OperationXY127410505X mod YX127410505XY105051274X mod YX3131274XY1274313X mod YX22313XY31322X mod YX522XY225X mod YX25XY52X mod YX12XY21X mod YX01XY10当Y=0时，输出X=1，所以1274和10505是互素的。7.4 对于字符串w=baba和下面的文法CFG G，试填写定理8.14中识别上下文无关语言的多项式时间算法中所描述的表。SRTRTR|aTRT|b解：TR,TSR,T,SRSSTR,TR7.5 下面的公式是可满足得吗？f=(xy)(x)(y)( )解:(x,y)共有四种取值：