2015年専門科目II
===

WTF

## 2
(1) $S(S^*T)=S^+T$であり、$T =S^0T$なので、$S(S^*T)+T=S^+T + S^0T=(S^+ + S^0)T=S^*T$
(2) $S^*T \subseteq L$を示せば良い。背理法で、$s^nt \notin L$だとする($n$は最小)。$n \geq 1$なら、$s^{n-1}t \in L$との兼ね合いで矛盾。$L \supseteq SL+T$が矛盾する。$t$($n$が0の時)を考えればよくて、$L \supseteq SL+T \supseteq T$だから、$L \supseteq T$なので示せた。連結は点を打ちなさい…
(3) $L_x=b \cdot L_z+a \cdot L_y+1$
(4) $L_y,L_z$についても式を立てて$L_y$について解く。以上。
(5d) 文字列は有限長なんだよなぁ。
$U \neq\emptyset$とすると、有限長の要素$u\in U$が存在する。そのようなものの中で最小の長さの文字列をとってきてこれを$v$とする。
すると、今$U\subseteq S\cdot U$が成り立つので、ある$v'\in U$と$s\in S$が存在して$v=sv'$とかけることになる。ところが、$S$が空語を含まないことから$|s|\geq 1$が成立しているので$|v'| \leq |v|-1$となり、$v$の文字列長の最小性に反する。矛盾。

## 3
(1)(a)v (b)U
(2)
アルゴリズムの出力した$T$について、$E(T)=\{e_{1},..,e_{n-1}\}$とおき、最適解のうち$i=min\{h\in\{1,...,n-1\}:e_{h}\notin E(T^*)\}$が最大となるものを$T^*$とおく。$T\neq T^*$と仮定して矛盾を導く。
$X\subseteq V(G)$を$e_{i}$が$\delta(X)$のminimun costの枝となり、$j\in\{1,..,i-1\}$について$e_{j}\notin\delta(X)$となるようにとる。すると、$T^*+e_{i}$は閉路$C$を含む。$e_{i}\in E(C)\cap\delta(X)$であることから少なくとも一本の$e_{i}$と異なる枝$f\in E(C)$で$f\in\delta(X)$となるものがある。
($\delta$は$X$から$V-X$へ伸びてる辺)
$(T^*+e_{i})-f$がspanning treeである。 ... (i)
また、$T^*$の最適性より$cost(f)\leq cost(e_{i})$が成立する。一方で、$f\in\delta(X)$なので$cost(f)\geq cost(e_{i})$も成立。 ... (ii)
よって(i),(ii)より$(T^*+e_{i})-f$も最適解となる。これを$T^{**}$とおくと、$min\{h\in\{1,...,n-1\}:e_{h}\notin E(T^{**})\}\geq i+1$となり$i$の最大性に矛盾。
(3)上の証明はコストの大小しか見ていないので負のものがあっても当然動作する。
(4)

## 4
(2)Half Adder: A + B -> S + Carry
Full Adder: Carry + A + B -> S + Carry

(4)

A11001110
B01100011
---------
11001110(桁上がり)
 10101101
---------
100110001

A11001110
B01100011
---------
CPCZCCPC
11001110

00:Z
01or10:C (carrier)
11:P (producer)


P
P   P
P Z C P 
CPCZCCPC

11001110

segment tree

35
26      9
11  15  2   7
5 6 7 8 1 1 2 5