Tree automata

今回は(one way) tree automataの話です. ざっくり直感的な説明をするなら、木構造をした入力テープ上を走査(ただし今回はone wayなので逆走したりはしない)して、そこに書かれたアルファベットを入力として読んでいき状態遷移するようなオートマトンなのですが、チ○ンラーメンで出来た*1私の貧相な脳みそでは理解するまでに苦戦を強いられてしまいました。そこで、同じチキ○ラーメンで出来た脳みそを持つ同士が心置きなく○キンラーメンを食べることができるようにちょっとした説明記事を書こうと思います。

話の流れとしてはまず定義を示し、その後意味のない例を用いて動きを確認していきます。

定義

定義 1 :

非負整数の初めのN個を0回以上繰り返して作れる列 $T_N = \left\{ 0,1,\dots,N-1 \right\} ^{*}$ をN分木とみなす. この時空列 $\Lambda$ は木のルートである. また, 各ノード $x \in T_N$ は後者(successors)として $x0,\dots,x(N-1)$ をもつ.

定義2:

$T_N$ の要素の列 $\pi = \left\{ x_n \right\}$ ですべての $n$ について $x_{n+1}$ が $x_n$ の後者になっているようなものをパスと呼ぶ.

定義3:

$\Sigma$ が有限のアルファベットであるとき, 関数 $f : T_N \rightarrow \Sigma$ を無限 $N$ 分 $\Sigma$ 木と呼ぶ.

定義4:

無限 $N$ 分 $\Sigma$ 木上の(非決定的)ツリーオートマトン $A$ は次の要素からなる4つ組 $(S, s_0, M, G)$ で定義される.

$S$ は状態の集合
$s_0 \in S$ は初期状態
$M : S\times \Sigma \rightarrow 2^{S^N}$ は次状態関数
$G \subset 2^{S}$ は受理部分集合

定義5:

$A$ の実行 $\rho : T_N \rightarrow S$ は $\rho (\Lambda)=s_0$ かつ任意の $x \in T_N$ について $(\rho (x0),\dots , \rho (x(n-1))) \in M(\rho (x), f(x))$ となるような関数

定義6:

$\rho$ が $f$ 上の $A$ の実行かつ $\pi$ が無限パスであるとき, $Inf(\rho, \pi) = \left\{ s \in S \mid \pi\ \texttt{上の無限にある} x \texttt{について}\ \rho (x) = s \right\}$

定義7:

すべての無限パス $\pi$ について $Inf(\rho, \pi) \in G$ となるような $f$ 上の $A$ の実行 $\rho$ が存在するとき、そしてその時に限り, オートマトン $A$ は無限 $N$ 分 $\Sigma$ 木 $f$ を受理する.

例:

定義は一通り示したわけですが、困ったことに脳みそがチキン○ーメンで出来ていると定義からその意味をイメージすることが出来ないわけです。ところが幸いなことにオートマトンの話なので動かしてみることが出来ます！というわけで具体的な例を考えていきます。

定義1で言っているのは, 木の各ノードを非負整数の列により表すことができるという事です。例として以下に皆が大好きな2分木の画像を張ります。 f:id:kashiwagi513:20161202201332p:plain

左からそれぞれ $T_2 = \left\{ \Lambda , 0, 1 \right\}$ , $T_2 = \left\{ \Lambda , 0, 1, 00 \right\}$ のようにして表すことができます. 左右の図中0,1はどちらも各々の $\Lambda$ の後者です。ここで, 右図中00は0の後者ではない, という事に注意してください。

この木の上でのたどり方をパスと呼びますがパスは定義2のようにして定義されます。たった今右図中の00は0の後者ではないといったのはパスの定義の際に0から直ぐに00へと移動するようなたどり方を許さないようにするためです。

さて、本題のオートマトンの話に移りましょう。例として次のようなオートマトンを考えます。

$S = \left\{ s_0, s_1, s_2, s_3 \right\}$
$M(s_0, a) = \left\{ (s_1, s_2) \right\}$
$M(s_0, b) = \left\{ (s_2, s_1) \right\}$
$M(s_1, a) = \left\{ (s_2, s_3) \right\}$
$M(s_1, b) = \left\{ (s_3, s_2) \right\}$
$M(s_2, a) = \left\{ (s_2, s_3) \right\}$
$M(s_2, b) = \left\{ (s_3, s_2) \right\}$
$M(\_, \_) = \left\{ \right\}$
$G= \left\{ s_0, s_1, s_2, s_3 \right\}$

簡単のためすべての状態を受理状態に含めました。つまりこれで非決定的な遷移の結果可能な遷移先がなくならなければ(実行が無限に続きさえすれば)受理するようになるはずです。また、簡単のため各次状態関数の遷移先の個数を0個か1個にしました。ここで、定義5をもう一度見てみましょう。

定義5:

$A$ の実行 $\rho : T_N \rightarrow S$ は $\rho (\Lambda)=s_0$ かつ任意の $x \in T_N$ について $(\rho (x0),\dots , \rho (x(n-1))) \in M(\rho (x), f(x))$ となるような関数

ここがすっきりとわかればもう実行の様子はイメージ出来るようになるはずです(少なくとも私の混乱の原因はここでした)。定義5に基づいて次の図の様な入力を与えた時の具体的な実行を求めてみましょう。

f:id:kashiwagi513:20161203011416p:plain

点々で表した以降の部分は直前のノード上のアルファベットと同じものが続くと考えてください。この時,定義5より実行 $\rho (\Lambda)$ は $s_0$ となりますね。では、ノード0,1時点での実行はどうなるでしょうか。ノード $\Lambda$ に対応するアルファベットは $a$ です。次状態関数より $M(\rho (\Lambda),f(\Lambda))=M(s_0,a) = \left\{ (s_1, s_2) \right\}$ となるので,ノード0,1に対応する実行はそれぞれ $\rho (0) = s_1, \rho (1) = s_2$ となります。同様にして各ノード時点での実行を求めていくと次のようになります。