浙江大学 2015-2016 学年 秋冬 学期

研究生《计算理论》课程期终考试试卷

考试形式: 闭卷, 考试时间: 2016 年 1 月 15 日, 所需时间: 120 分钟

学号: __________ 姓名: __________ 专业: __________ 任课教师: 金小刚

题序	1	2	3	4	5	6	7	总分
得分
评卷人

Zhejiang University

Theory of Computation, Fall-Winter 2015

Final Exam

1. (20%) Determine whether the following statements are true or false. If it is true write a $\backslash circ$ otherwise a $\backslash times$ in the bracket before the statement.

(a) ( ) Let $L$ be any regular language. Then the number of equivalence classes respect to language $L$ (i.e. $x\; \backslash approx\_L\; y$ , if for all $z\; \backslash in\; \backslash Sigma^*$ , $xz\; \backslash in\; L$ iff $yz\; \backslash in\; L$ ) is finite.

(b) ( ) The language $\backslash \{a^n\; b^n\; w\; |\; w\; \backslash in\; \backslash \{a,\; b\backslash \}^*,\; n\; \backslash in\; N,\; \backslash text\{\; and\; \}\; |w|\; =\; 2n\backslash \}$ is context-free.

(c) ( ) The language $\backslash \{\backslash text\{"M"\}\; \backslash text\{"w"\}\; |\; M\; \backslash text\{\; accepts\; \}\; w\; \backslash text\{\; in\; less\; than\; \}\; 2016\; \backslash text\{\; steps\}\; \backslash \}$ is not recursive.

(d) ( ) The language $\backslash \{\backslash text\{"M"\}\; |\; M\; \backslash text\{\; is\; a\; TM\; and\; \}\; L(M)\; \backslash text\{\; is\; Context-free\; but\; \}\; L(M)\; \backslash text\{\; is\; not\; regular\}\backslash \}$ is not recursive.

(e) ( ) The language $\backslash \{\backslash text\{"M\}\_1\backslash text\{"\; \}\; \backslash text\{"M\}\_2\backslash text\{"\; \}\; |\; M\_1\; \backslash text\{\; and\; \}\; M\_2\; \backslash text\{\; are\; TMs,\; and\; \}\; M\_1\; \backslash text\{\; halts\; on\; \}\; e\; \backslash text\{\; but\; \}\; M\_2\; \backslash text\{\; doesn\text{'}t\; halt\; on\; \}\; e\backslash \}$ is recursively enumerable, but not recursive.

(f) ( ) The set of all primitive recursive functions is a proper subset of the set of all $\backslash mu$ -recursive functions.

(g) ( ) Let $A$ and $B$ be two disjoint recursively enumerable languages. If $\backslash overline\{A\; \backslash cup\; B\}$ is also be recursively enumerable, then it is possible that neither $A$ nor $B$ is decidable.

(h) ( ) Let $H\_\{10\}\; =\; \backslash \{\backslash text\{"M"\}\; |\; M\; \backslash text\{\; is\; a\; TM\; and\; \}\; 10\; \backslash in\; L(M)\backslash \}$ and $\backslash tau\_1$ and $\backslash tau\_2$ are recursive functions. If $H\_\{10\}\; \backslash le\_\{\backslash tau\_1\}\; L$ and $\backslash overline\{H\_\{10\}\}\; \backslash le\_\{\backslash tau\_2\}\; L$ , then $L$ is recursive enumerable but not recursive.

(i) ( ) Suppose $\backslash mathbf\{SAT\}\; \backslash le\_P\; L$ and $L\; \backslash in\; \backslash mathbf\{P\}$ . Then $\backslash mathbf\{P\}\; =\; \backslash mathbf\{NP\}$ .

(j) ( ) Let $H\; =\; \backslash \{\backslash text\{"M"\}\; \backslash text\{"w"\}\; |\; \backslash text\{TM\; \}\; M\; \backslash text\{\; halts\; on\; input\; string\; \}\; w\backslash \}$ , then $H$ is $\backslash mathbf\{NP\}$ -complete.