浙大计算机00春博真题

2000年春博题目（是99年秋天考的）。 Ha q23K  
JK,#dA#
 
计算理论 nU`vj`K   
一、1、根据图灵机理论,说明现代计算机系统的理论基础。 ->8n
.!F}  
2、说明按乔姆斯基分类，语言、文法、自动机的关系 Jv7
@[<$  
DU}q4u@)  
一、   证明 HALT(X ` 1,X)不是可计算的。 jW
P(7}U  
Szwa2IdI.  
三、1、证明递归集都是递归可枚举集。 yKDg ~zsh  
2、举例属于递归可枚举集但不是递归集的集合，并证明之。 &^&k]JBaV  
<;v{`@
\j{  
四、1、证明L={（a，b）*|a，b的个数相同}为上下文无关语言? #i)h0ML/e  
2、并证明其不是正则的。