数理解析研究所講究録1093 巻 1999 年 212-217

212

Two-Point Splicing System の言語生成能力の万能性
細川英, 森田憲–, 岩本宙造, 今井克暢

H.Hosokawa, K.Morita, C.Iwamoto and K.Imai
広島大学工学部

Faculty of Engineering, Hiroshima University{hosokawa, morita, iwamoto,1$\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{i}$

近年、 splicing 規則に基づ$\mathrm{s}\mathrm{y}_{\mathrm{S}\mathrm{t}}\mathrm{e}\mathrm{m}$.

$\otimes \mathrm{k}\mathrm{e}.\mathrm{S}\mathrm{y}\mathrm{s}.\mathrm{h}\mathrm{i}\mathrm{r}\mathrm{o}\mathrm{s}\mathrm{h}\mathrm{i}\mathrm{m}\mathrm{a}-\mathrm{u}.\mathrm{a}\mathrm{C}.\mathrm{j}\mathrm{P}$

splicing 規則によって splice され $(y, z)$ が生成されたと言う (図 1)。

はじめに

splicing}$[1,2]$$<$

DNA 計算のシステムが新たなタイプの計算モデルとして注目されている。 Splicing system とは、 制限酵素とリガーゼの作用により DNA 分子が切断され、 それらが交差して再連結するプロセスをモデル化したものであり、 記号列の切断と連結を並列的に実行することで言語生成を行うシステムのことである。 しかし、 従来の splicing system では、 初期記号列集合と

splicing 規.

則集合が共に有限の場合、 生成される言語族が正規集合族にしかならないことが知られていた。 そこで、 本$\text{研究_{で}は従来のシステ_{ム}では}-$ 点であった切断部分を

図 1: Splicing system における規則の適用

二点に増やし、 切断と結合が同時に二点で起きるような二種類の two-point splicing system を提案する。 そ$R$を splicing 規則集合 (して、 初期記号列と splicing 規則の集合が有限の場合

るとき $\sigma=(V, R)$ をでも、 これらのシステムの言語生成能力が万能になる

意の言語とするとき、ことを示す。

2.

$\sigma(L)$.

,$\sigma^{0}(L)$

$=$

$L$

$\sigma^{i+1}(L)$$=$$\sigma^{i}(L)\cup\sigma(\sigma^{i}(L)),$$\sigma^{*}(L)$

$=$

$\#$

$\in$

は空列

$\epsilon$$\vdash_{\Gamma}$を次のように定義する。

$(w,x)$$\bigcup_{i\geq 0}\sigma^{i}(L)$を含む $V$ 上の記号列集合とする。 4 つの記

号列 $w,$ $x,y,$ $z\in V^{*}$ の間に成り立つ関係$\vdash_{\mathrm{r}}$iffは以下のようfor some $w,$ $x\in L,$ $r\in R,$ $z\in V^{*}$ },。

$V^{*}$とすを任or $(w,x)\vdash t(Z,y)$ ,$\mathrm{H}$$r$$\sigma(L),$ $\sigma^{n}(L),$ $\sigma^{*}(L)$$L\subseteq V^{*}$$\{y\in V^{*}|(w,.x)\vdash_{r}(y,z)$$=$

ここではまず従来の sphhcing system である extended$V$

scheme と呼ぶ。

に定義される。

Splicing Systemsystem について述べてお $<[1,2]$と $ を $V$ に属さない二つのをアルファベット、
特別な記号とずる。 Splicing 規則とは次のような をいう: $r=u_{1}\# u_{2} u_{3}\# u_{4}$ (V*#V*$V*#V*). 但し、$\mathrm{H}$$R\subseteq V^{*}\#^{\mathrm{v}^{*}} V^{*}\#^{\mathrm{v}^{*})}$

そして、 extended$\mathrm{H}$$i\geq 0$,.

system は以下のように定義される。

$(y,z)$$\gamma=(V,T,A, R)$.

$w=w_{1}u_{1}u_{2}w_{2},$$y^{=w_{1}}u_{1}u4x_{2},$for some$x=x_{1}u_{3}u_{4}X_{2}$,$z=x_{1}u_{3}u_{2^{W_{2}}}$,$w_{1},w_{2},x_{1},X_{2}\in V^{*}$

ここで $V$ はアルファベット、$T$ は終端記号集合$A$は初期記号列 (axiom) 集合.

$u_{1}u_{2},u_{3}u_{4}$$(A\subseteq V^{*})_{\text{、}}R$$(T\subseteq V)_{\text{、}}$

は splicing

規則集合 (RV*#V*$V*#V*) である。
そして、この関係が成り立つとき $w,x$ がサイト.

で$\gamma$によって生成される言語に定義される。

$L(\gamma)$

は次のよう

213

$L(\gamma)=\sigma^{*}(A)\cap\tau^{*}$$F_{1},$$F_{2}$.

を任意の言語族とする。 $A\in F_{1},$ $R\in F_{2}$ であるような extended$\mathrm{H}$system $\gamma=(V, T, A, R)$ によって得られる言語族は $EH(F_{1}, F_{2})$ と記される。 疏を縦にを横に、有限言語族 (FIN)、正規言語族 (REG)、線$F_{2}$形言語族 (LIN)、文脈自由言語族 (CF)、文脈依存言語族

図 2: Two-point splicing system tyPe I

帰納的可算言語族 $(RE)$ のそれぞれの場合を示すと表 1 のようになる [1]。但し、疏が線形で乃が有$(CS)_{\text{、}}$限の場合の表中の $L,$ $CF$ は $LIN\subset EH(F_{1}, F_{2})\subseteq CF$を示す。

して、 splicing 規則 $r=u_{1}\# u\# u_{2} v_{1}\# v\# v_{2}$ に対して
$V^{*}\cross V^{*}$

上の関係$\vdash_{r}$を次のように定義する。

Set of splicing rules$(w,x)$$\vdash_{r}$iff$\mathrm{g}\circ$$(y, z)$$w=w_{1}u_{1}uu2w_{2},$$x=x_{1}v_{1}vv2x2$$y=w_{1}u_{1}vu_{2}w_{2},$$z=x_{1}v_{1}\mathrm{c}\iota v_{2^{X}2}$$.\overline{\infty\epsilon.\mathrm{g}\circ}$

for some$w_{1},$ $w_{2},$ $x_{1},$ $X_{2}\in V^{*}$$\mathrm{H}$,.

Extended system の場合と同様に、これを $y,$ が $w,$
から splicing によって得られたという。
を splicing 規則集合
をアルファベット、$\mathrm{H}$

Table 1:Extended
言語族 [1],system により生成される

$z$

$V$

$R$

$x$

$(R\subseteq$

V*#V*#V*$V*#V*#V*) とするとき $\sigma_{I}=(V,R)$ を
TPS Ischeme と呼ぶ。

しかし、 表で示されるように、 このシステムでは与き、$L\subseteq V^{*}$$\sigma t(L),$ $\sigma_{t}^{n}(L),\sigma^{*}I(L)$

を任意の言語とするとを次のように定義する。

えられた初期記号列と sphicing 規則の集合が有限の場
合、 正規集合族しか導くことが出来ない。

$=$$\sigma_{I}(L)$

そこで、 本研究では以下に示すような二種類の two-

point splicing system を提案し、 これらのシステムが初期記号列と splicing 規則の集合が有限の場合でも言$\text{語生成能力が万能となる}$ (つまり、 $RE$ を正確に特徴づける) ことを示す。

$\{y\in V^{*}|(w,x)\vdash_{r}(y, z)$or$(w, x)\vdash_{\Gamma}(z,y)$for some $w,$ $x\in L,$ $r\in R,$ $z\in V^{*}$ },

,

$=$

$L$

$\sigma_{I^{+}}^{i1}(L)$$=$$\sigma_{I}^{i}(L)\cup\sigma_{t(}\sigma t(iL)),$$\sigma_{I}^{*}(L)$$=$$\sigma_{I}^{0}(L)$$\bigcup_{i\geq 0}\sigma_{I}^{i}(L)$3

Two-point splicing system
type I (TPS I system)

3.1

定義

ここで $V$ はアルファベット、$T$ は終端記号集合$A$は初期記号列 (axiom) 集合$\in$$(T\underline{\subseteq}V)_{\text{、}}$, $ を用いて、 $r=u_{1}\# u\# u_{2} v1\# v\# v2$

V*#V*#V*$V*#V*#V*) によって表される。 そ$(A\subseteq V^{*})_{\text{、}}R$

は splicing

規則集合 (RV”#V*#V*$V*#V*#V*) である。
そして、$\delta_{I}$によって生成される言語$L(\delta_{I})$を次のように定義する。 但し、 $\sigma_{I}=(V, R)$ とする。
$L(\delta_{I})=\sigma_{I}^{*}(A)\cap\tau^{*}$のであり、 アルファベット $V$ と $V$ に属さない二つの$\#$.

$\not\geq$

点で切断し、 その間の記号列を交換するかを示したも
特別な記号

,

.

$\delta_{I}=(V,\tau,A, R)$$\mathrm{s}\mathrm{y}8\mathrm{t}\mathrm{e}\mathrm{m}$$i\geq 0$

そして、 TPS Isystem を次のように定義する。

Two-point splicing
type I (TPS I system)
は、従来の splicing 操作では一ケ所であった切断部分を
図 2 のようにニケ所に増やし、その間の記号列を交換するといった splicing 操作を行うシステムのことである。
TPS Isystem 上の splicing 規則は、 どのように二(,$F_{1},$$F_{2}$.

を任意の言語族とする。 $A\in F_{1},$ $R\in F_{2}$ であるような TPS Isystem $\delta_{I}=(V,T,A, R)$ によって得214(II) $n=k+1(k\geq 0)$ のとき, こ対して (1) が満たされていとなるような任意の についると仮定する。

られる言語の族を.

. $TP_{I}(F_{1,2}F)$

$-$

$-$

.

$n’\leq k$ である任意の $n’$$\cdot$$s^{k}\Rightarrow^{1}G\eta$$\eta$て考える。 このとき、 あると記す。

$\eta’$が存在し、$s\mathrm{g}_{\eta’}G\Rightarrow\eta G$となる。 従って、 ある書換規則 $\alphaarrow.\beta(\in P)$ が存在

TPS Isystem による帰納的可算言語

3.2

の特徴づけ

し、 ある

$\eta=\eta_{0}\beta\eta_{1}$則$\eta_{1}\in(N\cup T)^{*}$$\eta 0,$に対して、$\eta’=\eta 0^{\alpha\eta_{1}}$,と表わすことができる。 このとき splicing 規$r_{1}=\#\alpha\# x\#\beta\#\mathrm{Y}$により次のようになる。

次の定理 31 は TPS Isystem で生成される言語族が帰納的可算言語族と –致することを示している。

(注) TPS Isystem は後で示す TPS II system を特殊な場合として含んでいるので、定理 31 は TPS II systemが帰納的可算集合族を特徴づけるという結果 (定理 41)
から系として得られる。 しかし、 TPS Isystem の場合には、 任意の$0$

塑文法に対して、 それを直接的に模倣するシステムが容易に構成できるので、 ここではそのような方法による証明を与えることにする。

$\vdash_{\mathrm{r}}1$
仮定より
で、$\eta’\in\sigma_{I}^{k}(A)$$\eta\in\sigma_{I}^{k+1}(A)$

したがって

.

が成り立ち、 $X\beta Y\in A$ であるのである。

$(\mathrm{I})(\mathrm{I}\mathrm{I})$より(1) が成り立つ。 ((1) の証明

終)(2) 任意の $\eta\in(N\cup T)^{*}$ に対して、$\eta\in\sigma_{I}^{m}(A)$ならば

定理 31 $TP_{I}$ (FIN, $FIN$ ) $=RE$ .

(a)

(証明)

$s\Rightarrow\eta G$となる $n\leq m$ が存在する。

または、任意に与えられた$0$型文法 $G=(N, T, P, s)$ に対して、 $L(G)=L(\delta_{I})$ となるような TPS Isystem$\delta_{I}$は次(b) ある $\xi\in(N\cup T)^{*}$ に対し、 $\eta=X\xi Y$ と書ける。

のように構成できる。 但し、 $N$ は非終端記号集合、 $T$

は終端記号集合 $(N\cap T=\phi)_{\text{、}}P$ は書換規則集合、 そ(2) の証明

して、 $S$ は開始記号とする。
$\delta_{I}=(V,\tau,A, R)$$(\mathrm{I})m=0$.

$\sigma_{I}^{0}(A)=A$

のとき

より、

$\eta=S$ のときは$\eta$

は $S$ か$s\mathrm{A}_{\eta}G$$X\beta \mathrm{Y}$の形の記号列となる。

であるので (a) を、 $\eta=X\beta Y$ のときは (b) を満たす。 よって $m=0$ のときは成り立つ。
$V$

$=$

$N\cup T\cup\{X, \mathrm{Y}\}$

但し、
$A$

$=$

$R$

$=$

$(\mathrm{I}\mathrm{I})m=k+1(k\geq 0)$$X,\mathrm{Y}\not\in(N\cup T)$とする,$\{S\}\cup\{X\beta \mathrm{Y}|\alphaarrow\beta\in P\}$のとき

$m’\leq k$ であるような任意の $m’$,

つと仮定する。 任意の$\eta\in\sigma_{I}^{k}(A)$とする.

$\{\#\alpha\# x\#\beta\#\mathrm{Y} |\alphaarrow\beta\in P\}$に対して (2) が成り立$\eta\in\sigma_{I}^{k+1}(A)$について考える。

のときは帰納法の仮定より成り立っている

ので、 $\eta\in\sigma_{I}^{k+1}(A)-\sigma^{k}(t)A$ とする。 $R$ 中の splicing 規

定理を証明するために次の (1) (2) を帰納法で証明する。 但し、$\eta\Rightarrow G\zeta$

は文法 $G=(N, T, P, s)$ において $P$

中の書換規則により$\eta$から$\zeta$を導出することを示し、則がすべて #\alpha #$X#\beta #Y $(\in R)$ という形をしている
ことと、$\eta’\in\sigma_{I}^{k}(A),$$\eta$$\Rightarrow G$の反射 推移閉包を示している。 またから$\zeta$$\eta\Rightarrow^{\acute{t}}\zeta c$$\text{、}$は力 s ステップで得られることを示す。

(1) 任意の $\eta\in(N\cup T)*$ に対し、$\eta\in\sigma_{I}^{n}(A)$$S\Rightarrow G\eta$の各要素が (2) を満たすことから、 ある$X\beta Y\in\sigma_{I}^{k}(A),$$\Rightarrow^{*}G$

$R)$

は

$\sigma_{I}^{k}(A)$

ならは

および、

$\zeta\in V^{*}$$r=$ #\alpha #$X#\beta #Y $(\in$が存在して次のような splicing が起こる。

$\vdash_{r}$

となる。

.

このとき splicing 規則の形により、(1) の証明$\cdot$$\eta,$$\zeta$が $X\alpha Y$ となる。 $\eta=X\alpha Y$ のときは (2)のどちらか$(\mathrm{b})$を満たすので、 以下では $\eta\neq X\alpha Y$ とする。

(I) $n=0$ のとき$\eta=_{\iota}S$であるので明らか。

$\eta’=X\xi’Y(\xi’\in(N\cup T)^{*})$ の場合、$\alpha,$$\beta\in(N\cup T)*$であるため、 ある $\xi\in(N\cup T)^{*}$ に対して、 $\eta=X\xi Y$215と書けなければならない。 よって、 この満たす。 また、 ある $n’\leq k$ に対して、$\eta$は (2)$(\mathrm{b})$を’ となる場,$s\acute{\mathrm{s}}_{\eta}$$G$

算言語族が–致するということを示す次の定理 41 が成り立つ。

合は、 $\eta’=\eta 0\alpha\eta 1(\eta_{0}, \eta_{1}\in(N\cup T)^{*})$ と書ける。 よって、}$\beta\eta_{1\eta}=G$$S^{n’}\Rightarrow\eta 0\alpha\eta 1G\Rightarrow lK$となり、 この$\eta$は (2)$(\mathrm{a})$定理 4.1 $TP_{II}$ (FIN, $FIN$ ) $=RE$ . .

を満たす。 よって $m=k+1$ のときも (2) は成り立つ。

従って、(1) (2)$S\Rightarrow^{*}\eta G$$(\mathrm{I})(\mathrm{I}\mathrm{I})$(証明)

より (2) が成り立つ。 ((2) の証明終)$G=$ ( $\{S,$ $A,$ $B,C\},T,s$ , Pu $\{ABCarrow\epsilon\}$ )$\mathrm{e}\mathrm{k}\text{り}$iff

標準形 [2] であるような任意の文法とする。 但し、 $T$$\eta\in\sigma_{I}^{*}(A)\cap(N\cup T)^{*}$が得られ $L(G)=L(\delta_{t})$ が証明された。

Geffert$\text{を}$口は終端記号集合、 $S$ は開始記号、 $P$ は書換規則集合で$Sarrow uSv,$ $Sarrow x\in P(u, v, x\in(T\cup\{A, B, C\})^{+})$ である。 $G$ を模倣する TPS II system は次の通り。

4

Two-point splicing system
type II (TPS II system)41

定義

TPS Isystem の特別な場合として、 システム中の全ての splicing 規則が V*#V*#V*$V*#\epsilon #V* の要素で$\delta_{It}=(V,\tau, A,R)$

$V$

$=$

$\{S_{1}, S2, A, B, c,L, M, X, Y\}\cup T$

$A$

$=$

$\{s_{1}s_{2}\}\cup\{XLus_{1}s_{2}vMY|Sarrow uSv\in P\}$$\cup\{XLwMY|Sarrow w\in P\}$

あるようなシステムを考える。 このシステムは、 –方の部分記号列をもう –方の記号列に挿入するといった

TPS Isystem よりシンプルな splicing 操作のみ行うシ,$\cup\{XY\}$$R$$\{X\# Lus1s_{2}vM\#\mathrm{Y} S1\# S2|Sarrow uSv\in P\}$$=$

ステムである (図 3)。

$\cup\{X\# LwM\# Y s1\# S_{2}|Sarrow w\in P\}$$\cup\{\# ABC\# X\# Y\}$$\cup$$f$:{ $\# s_{1}L\# x\# Y$, #MS2#$X#Y} とする.

$(\{S, A, B, c\}\cup T)^{*}$$(\{S, A, B, c\}\cup T)^{*}$

1.

は$f(\eta)$$\eta$$arrow V^{*}$

と

$g$

:

$V^{*}$$arrow$を次のような関数として定義する。

中の全ての $S$ を$S_{1}S_{\mathit{2}}$に置き換えて得られる列

図 3: Two-point splicing system tyPe II

このシステムを TPS II system と呼び、$\delta_{II}.=(V,T,A,R)$

2.

は$g(\xi)$$S_{1}S_{2}$$\xi$

中の全ての部分列 $S_{1}L$ と $MS_{2}$ を消去し、を $S$ に置き換えて得られる列

このとき次の (1) (2) が成り立つ。 (但し、 $\sigma_{II}=(A, R)$である。 )(1) 任意の $\eta\in(\{S, A, B, \mathit{0}\}\cup T)^{*}$ に対して

$s\Rightarrow\eta G$

ならば $f(\eta)\in\sigma_{It}^{*}(A)$とする。 それぞれの記号は TPS Isystem のときと同様(2) 任意のである。 但し、 このシステムの splicing 規則を以下では(a)$r=u_{1}\# u\# u_{2} v_{1}\# v_{2}$と記述する。 また、 $\sigma_{II}=(V, R)$

4.2$\xi\in\sigma_{II}^{m}(A)$ならば、$S\Rightarrow^{*}g(G\xi)$ 。

(b) ある $\xi’\in V^{*}$ が存在して、 $\xi=X\xi\prime Y$ と書ける。

TPS II system による帰納的可算言語の特徽づけ$TP_{tI}(F_{1}, F_{\mathit{2}})$

に対し、

または、

を $\sigma_{I}=(V, R)$ と同様とし、 TPS II scheme と呼ぶことにする。

$\xi\in V^{*}$

を $TPt(F_{1}, F2)$ と同様の言語族とする

とき、 TPS II system で生成される言語族と帰納的可

そこで、 この (1)(2) の証明を行う。

(1) 任意の $\eta\in(\{S, A, B, c\}\cup T)^{*}$ に対して
ならば $f(\eta)\in\sigma_{It}^{*}(A)$$s\Rightarrow\eta G$

216(1) の証明と書ける。 $r_{1}=$ #ABC#$X#Y $\in P$ とす$\eta=\eta 0\eta_{1}$

ると、(I) $n=0$ のとき.
$\eta=S$ であるので $f(\eta)=f(S)=S_{1}S_{\mathit{2}}\in A$$(\mathrm{I}\mathrm{I})n=k+1(k\geq 0)$と仮定する。

$s^{k}\Rightarrow^{1}\eta G$

このとき、 ある
こで、のときである。 帰納法の仮定より $f(\eta’)\in\sigma_{II}^{*}(A)$ であり、 まであるような任意の $n’$ に対して (1) が成り立つ$n’\leq k$$\eta’\Rightarrow\eta G$$\eta’$であるような任意のが存在し、$\eta$$s4_{\eta’}G\Rightarrow\eta G$を考える。

となる。 この導出に用いられる書換規則の形によって次の三通りの場合$(\mathrm{i})(\mathrm{i}\mathrm{i})(\mathrm{i}\mathrm{i}\mathrm{i})$に分ける。

(i) 書換規則 $Sarrow uSv\in P$ の場合 :ある$\eta 0,$$\eta_{1}\in(\{A, B, C\}\cup\tau)^{*}$$\eta 0uSv\eta_{1}$$r_{2}$に対して $\eta’=\eta 0^{S\eta}\eta 1,=$と書ける。 $r_{1}=X\# Lus_{1}S_{2}vM\# Y S_{1}\# S_{2}$ ,$=$$\vdash_{r_{1}}$となり、が成り立つ。

$f(\eta)\in\sigma_{II}^{*}(A)$$\#^{s_{1}}L\# x\# Y$$(r_{1},r_{2}, r_{3}\in P)$,$r_{3}$#MS2#$X#Y

$=$

とすると、

$\vdash_{r_{1}}$ .

$\vdash_{r_{2}}$ .
$\vdash_{t_{3}}.$ .
である。帰納法の仮定よりた $X\mathrm{Y}\in A$ であるので、 $f(\eta)\in\sigma_{JI}^{*}(A)$ となる。

よって、 これらのことより $n=k+1$ のときでも (1)が成り立つ。
したがって、れた。 ((1) の証明終)(2) 任意の(a)$\xi\in V^{*}$(b) ある$\xi’\in V^{*}$(I) $m=0$ のとき(ii) 書換規則 $Sarrow w\in P$ の場合 :であるので$XLwM\mathrm{Y},$の形の記号列のみである。 したがって$X\mathrm{Y}$$\xi=S_{1}s2$ のとき

(2)

$\xi$

を満たし、

$(\mathrm{a})$$\xi$がそれ以外のときを満たす。

$(\mathrm{b})$であるような任意の $m’$ に対して (2) が成り立考える。 もし、がって、 ある$\eta’=\eta_{\mathit{0}}S\eta_{1}$,$\xi\in\sigma_{tt^{1}}^{k+}(A)$$\xi\in\sigma_{II}^{k}(A)$$\mu,$であるような任意の

$\xi$

を

ならば帰納法の仮定から (2)$\xi\in\sigma_{II}^{k+1}(A)-\sigma_{I}^{k}(IA.)$$\nu\in\sigma_{II}^{k}(A)$とする。 したと $\zeta\in V^{*}$ および$\mathrm{r}\in R$

が

存在して

と書ける。 $r_{1}=X\# LwM\# Y S1\# s2,$ $r_{2}=$.

$(r_{1},r_{2},r_{3}\in P)$$\mathrm{c}\vdash_{r}$

.

とすると、

は $s_{1}s_{2},$ $xLuS1s2vMY$ ,$\xi\in\sigma_{II}^{0}(A)=A$が成り立つので、#MS2#$X#Y

が存在して、 $\xi=X\xi lY$ と書ける。

(2) の証明$m’\leq k$となる。

$\#^{s_{1}}L\# x\# Y,$ $r_{3}=$

ならば、

または、

つと仮定する。

$\eta=\eta_{0}w\eta 1$$\xi\in\sigma_{II}^{m}(A)$(II) $m=k+1(k\geq 0)$ のとき$f(\eta’)=\eta_{\mathit{0}}s_{1}S_{2}\eta_{1}\in\sigma_{II}^{*}(A)$ある $\eta 0,\eta_{1}\in(\{A, B, c\}\cup T)^{*}$ に対してに対し、

$S\Rightarrow^{*}gG(\xi)\text{。}$は (2)であり、 また $XLus_{1}s2vM\mathrm{Y},$ $xY\in A$ であるので、$f.(\eta)\in\sigma_{II}^{*}(A\rangle$より (1) が成り立つことが証明さ$(\mathrm{I})(\mathrm{I}\mathrm{I})$と書くことができる。 ここで規則通りの場合$(\mathrm{i})(\mathrm{i}\mathrm{i})(\mathrm{i}\mathrm{i}\mathrm{i})(\mathrm{i}\mathrm{V})$$r$の形により次の四に分ける。

(i) $r=X\# LuS_{1}s_{2}vM\# Y s1\# S2$ の場合 :$(\text{領野^{}\eta}1)\vdash_{\mathrm{r}_{2}}$帰納法の仮定および.

$r$の形から、 ある$\mu 0,$ $\mu_{1}\in V^{*}$に対して $\mu=\mu 0S1S_{2}\mu_{1}\text{、}$ かつ $\nu=XLuS1s\mathit{2}vMY$ と書ける (が入れ替わっている場合も同様なので以下でのどちらかが $XY$ となる。 $\xi=XY$は略)。このとき
$\mu$

と

$\nu$

$\xi,$のとき (2)

まず、である。 帰納法の仮定より $f(\eta’)\in\sigma_{II}^{*}(A)$ であり、 ま
た $XLwM\mathrm{Y},XY\in A$ であるので、なる。

$f(\eta\rangle$.

$\in\sigma_{II}^{*}.(A)$と$\eta’=\eta_{\mathit{0}^{A}}Bc\eta_{1}$を満たすので以下では $\xi\neq XY$ とする。

(2)$(\mathrm{b})$,を満たす場合、 つまりと書ける場合、

$\mu$

$\xi$

は (2)

$(\mathrm{b})$$=$の形のために、と書けなければならない。
が (2)を満たす。 次にを満$r$$\xi=X\xi’\mathrm{Y}(\xi’\in\dot{V}^{*})$

たす場合、 つまり、

(五 i) 書換規則 $ABCarrow\epsilon\in P$ の場合 :ある $\eta 0,\eta_{1}\in(\{A,B, C\}\cup\tau)^{*}$ に対して

$\mu$

が

$\zeta$$X\mu’Y(\mu’\in V^{*}.)$のとき:$(\mathrm{b})$

こ

$\mu$

$S\Rightarrow^{*}Gg(\mu)$$\xi=\mu 0S_{1}Lus_{1}S_{2}vMS_{2}\mu_{1}$$(\mathrm{a})$となる場合を考える。

となるので、 $S\Rightarrow^{*}Gg(\mu)=$

217
とな

となり、 従って $L(G)=L(\delta_{II})$ が成り立つことが証明を満たす。 よって、 この形の規則された。 つまり、 定理である $TP_{II}$ (FIN, $FIN$ ) $=RE$$g(\mu 0s_{1}S_{2}\mu_{1})\Rightarrow g(\mu_{0}s_{1}LuGS_{1}S2vMS_{\mathit{2}}\mu 1)=g(\xi)$

り、 この

$\xi$

は (2)

を用いた

$\xi$

は (2) を満たす。

$(\mathrm{a})$が証明された。

口(\"u) $r=X\# LwM\# Y s_{1}\# S_{2}$ の場合 :帰納法の仮定および$r$の形から、 ある$\mu 0,$ $\mu_{1}\in V^{*}$に対して $\mu=\mu 0S_{1}S2\mu 1\text{、}$ かつ $\nu=XLwM\mathrm{Y}$ と書ける。
このとき
き (2)

$(\mathrm{b})$$\xi,$$\zeta$のどちらかがを満たすので以下では$\mu=X\mu Y’(\mu’\in V^{*})$

$\xi$

は (2)

$(\mathrm{b})$となる。 $\xi=X\mathrm{Y}$ のとと書ける場合、 の形のために、$r$を満た凱 次にとなる場合を$S\Rightarrow^{*}g(\mu)G$考える。 $\xi=\mu_{0}s_{1}LwMs_{2}\mu_{1}$ となるので、$S\Rightarrow^{*}gG(\mu)=$$g(\mu 0S_{1}S_{2}\mu_{1})\Rightarrow Gg(\mu 0s_{1}LwMS2\mu_{1})=\mathit{9}(\xi)$

の

$\xi$

は (2)

た

$\xi$

は (2) を満たす。

$(\mathrm{a})$

となり、

こ

を満たす。 よって、 この形の規則を用い(iii) r=#ABC#$X#Y の場合 :帰納法の仮定および

$r$

5

とする。

$\xi\neq X\mathrm{Y}$と書けなければならない。 このと$\xi=X\xi\prime Y(\xi’\in V^{*})$

き$X\mathrm{Y}$まとめ
本研究では splicing system の新しいタイプとして、二ケ所で記号列を切断し、 その間の部分記号列を交換する two-point splicing system type I を提案した。 そしてこのシンプルなシステムは、 従来の– ケ所で切断するシステムとは異なり、 初期記号列と splicing 規則の集合が有限の場合でも帰納的可算集合族を特徴付けることを示した。 さらに、 –方の記号列から部分記号
列を取り出し、 もう –方に挿入するといった tyPe I のサブクラスである tyPeの形から、 ある$\mu_{1}\in V^{*}$$\mu_{0},$に対$\mathrm{I}\mathrm{I}$を提案し、 このシステムにおいても type I と同様の能力があることを証明した。

して $\mu=\mu 0^{ABc_{\mu 1}}\text{、}$ かつ $\nu=X\mathrm{Y}$ と書ける。 このとき$\xi,$のどちらかが XABCY となる。 $\xi=XABCY$$\zeta$のとき$(\dot{2})(\mathrm{b})$を満たすので以下では $\xi\neq XABCY$ と

する。

参考文献
[1] T.Head,D.Pixton, Language theory and molecular genetics: generative mechanisms suggested by DNA recombination, Handbook of Formal Languages, Vol.2 (G.Rosenberg,
A.Salomaa,), pp.295-360, Springer (1996).
$\mathrm{G}.\mathrm{P}\dot{\mathrm{a}}\mathrm{u}\mathrm{n},\dot{\mathrm{a}}\mathrm{n}\mathrm{d}$$\mu=X\mu’Y(\mu’\in V^{*})$と書ける場合、$r$の形のため、 $\xi=X\xi’\mathrm{Y}(\xi’\in V^{*})$ と書けなければならない。
このとき

$\xi$

は (2)

を満た凱 次に、$(\mathrm{b})$$S\Rightarrow^{*}g(\mu)c$

る場合を考える。 $\xi=\mu 0\mu 1$ となるので、$g(\mu 0^{AB}c\mu_{1})\Rightarrow Gg(\mu_{0}\mu 1)=g(\xi)$とな$S\Rightarrow^{*}gG(\mu)=$となり、 この(2)を満たす。 よって、 この形の規則を用いた(2) を満たす。
(iv) $r=\#^{s_{1}}L\# x\#\mathrm{Y}$ の場合 :

$\xi$

は

$\xi$

は

$(\mathrm{a})$帰納法の仮定および$r$の形から、 ある崗,$\mu_{1}\in V^{*}$$\zeta$(2)のどちらかが$(\mathrm{b})$$.XS_{1}L\mathrm{Y}$に対$\xi=X\xi’Y(\xi’\in V^{*})$$\xi$となる。 $\xi=XS_{1}L\mathrm{Y}$ のときは (2)$(\mathrm{b})$と書ける場合、の形のため、と書けなければならない。このときを満た凱次にる。 $\xi=\mu_{0}\mu 1$ となるので、$g(\mu 0\mu_{1})=g(\xi)$$r$$S\Rightarrow^{*}gG(\mu)$て、 この形の規則を用いたとなる場合を考え$S\Rightarrow^{*}\mathit{9}(\mu)=gG(\mu_{\mathit{0}}s_{1}L\mu_{1})\Rightarrow G$となり、 この
$\xi$

$\xi$

は (2)

$(\mathrm{a})$を満たす。 よっは (2) を満たす。

(v) r=#MS2#$X#Y の場合 :(iv) と同様である。

. よって、 (i)(\"u)(iii)(iv)(v) より $n=k+1$ のとき成り立つ。 したがって$(\mathrm{I})(\mathrm{I}\mathrm{I})$から (2) が成り立つ。 ((2) の証明終)
この (1) (2) より$\eta\in(\sigma_{tt(A)}^{*}\cap(V-\{X,Y\})^{*})$

iff$S\Rightarrow^{*}gG(\eta)$, G.Rozenberg and A.Salomaa, DNA Computing New Computing Paradigms, Springer$\mathrm{G}.\mathrm{p}\dot{\mathrm{a}}\mathrm{u}\mathrm{n}$(1998).

を満たすので以下では $\xi\neq XS_{1}LY$ とする。

$\mu=X\mu Y’(\mu’\in V^{*})$[2]-

して $\mu=\mu 0S_{1}L\mu 1$ かつ $\nu=X\mathrm{Y}$ と書ける。 このとき$\xi,$$\mathrm{e}\mathrm{d}\mathrm{s}.$