More than 5 years have passed since last update.

Kichigai-FriendsAdvent Calendar 2017Day 22

オートマトンをつつく

Last updated at 2017-12-23Posted at 2017-12-23

当記事はKichigai-Friends Advent Calendar 2017, 22日目の記事にあたります。

最も単純な数学モデルの一つであるオートマトンの概要から最近思いついた複雑系に関する軽い応用についてささっと今後も書いていきたいと思います.

拙いところ, 間違えてるところ, 怪しいところがあった場合はバンバンコメントにて投げてください, ディスカッションとサーベイで圧倒的成長です. アドベントカレンダー書くのはこれが初めてですが頑張りたいと思います.

このアドベントカレンダーではあるテーマに関する記事を集めているわけではなく

基本ホームレスな兄ちゃんが"多目的最適化をPSOでとく入門記事"を書いてたり
柏のプログラミング教育貴公子が"日本語ラップとプログラミング教育の類似点考察記事"を書いていたり
機械学習の兄ちゃんが"TensorRTを使ったインファレンスの高速化"を書いていたり(12/24投稿予定)

といったように, 各々が好きなことについて書いているカレンダーになっているようです.
とても他の人たちの記事も面白かったのでぜひとも一緒に見ていってください.

導入(歴史)

tl;dr

オートマトンは強い

オートマトン理論の歴史というのは, だいたいコンピュータ, 計算機の年齢とだいたい同じで, 1930年代までさかのぼることができます.

最初にその直接的な片鱗を確認することができるのはA.Turingの論文の中です. "計算機のできること, できないことの境界"について考えたら最終的に, 外部記憶と書き込みを内包したモデルに計算をさせるとかいうシステム, チューリングマシン¹なんて思いついたぞ, と大雑把に言うとそういう事が書かれているのですが, 正にそのモデルの部分に後のオートマトン理論を示唆する内容を見ることができます.

後に, 有限オートマトンという形で抽象化され体系化されたオートマトン理論は様々な分野へと出荷されていきます. 1940年代には20世紀のダヴィンチと言われているノイマンのアプローチをきっかけに"自己複製オートマトン理論"が作られ, ワトソンとクリックがDNAの二重らせん構造, 半保存的複製を発見するよりも前にDNAの性質について詳しく考察できていたことは有名です.

この流れはセルオートマトンと呼ばれる今でも使われるようなライフゲームなどで有名な複雑系関係へのアプローチのキーパーツ(c.f. カオスの縁)として使われたり, 脳のシミュレーションとしての応用などもされていきます.

一方で生物学界隈以外でもオートマトン理論はツールとして広がっていき, 1950年代後半にはチョムスキーという言語学者にわたり, 形式文法という形で姿を変え, 抽象的なオートマトンと文法とのかかわり方について当時の数学者からの注目を集めました. 結果としてコンパイラ等の基礎理論として我々は使っていますね.

このように, オートマトン理論は計算理論の基礎として, また非常に汎用性の高いツールとして, 現在非常に多くの分野でその応用系を見ることができます. ツールとして大きく広がった理由の一つに, 数理モデルとの相性があげられるでしょう.

現代の科学では, ある現象を数式で表す, 現象の数理モデル化をする時には, よく現象の状態遷移に注目して数式を立てます.

例えば, 車の渋滞モデルであったり, メトロノームの同期現象であったり, というのは漸化式を用いて表す事が可能ですが ², 漸化式って, つまるところ前の状態を引数として次の情報を返す関数のことですよね?
ある状態と次の状態の変化を表す漸化式を使ってモデルが組まれるということは, 状態遷移がポイントということは, なんとなくみなさんわかるとは思います.

この現象を状態遷移を基本単位として考えるという方法こそ, オートマトンの基本的な考え方そのもので, ツールとして多種多様に使える理由になります.³

こうして, とても単純でいてそして奇麗な数学モデルは, コアである計算理論では"CS界の線形代数"⁴として, ツールとしてはモデル化の方法として, どちらに対しても発展を遂げており, 現在のサイエンスを理解するうえで非常に有用な切り口の一つになることは明らかです.

今回から始まる記事群で皆さんのオートマトンに対する理解がちょっとでも深まってくれるとうれしいです.

基礎知識

方針としては初めに決定性有限オートマトン(DFA)の話を徐々に拡張していき, 非決定性有限オートマトン(NFA), ε動作について説明していきます. と, その前に基礎的なオートマトン理論ででてくる用語の説明と基礎概念を解説

用語 / 基礎概念

オートマトン理論にてメインとなる"問題", とは "ある文字列が特定の集合に属するかどうかの決定"というものになります.

じつは世の中一般的に我々が問題と呼んでいるものは, このオートマトン理論を介して考察すると, ある言語に対する帰属問題として表すことができます.

この"問題"をもっと形式的に言うのであれば,

ΣがアルファベットでLがΣ上の言語であるとき, 問題Lとは,
与えられた$Σ^*$の中の文字列ωについて, ωがLの中にあるか否かを決定せよ.

まずは, この"問題"を理解するために, オートマトン理論でとてもよく出てくる言葉三つを理解しましょう.

アルファベット(記号の集合)
文字列 (アルファベット上の記号を組み合わせてできる記号の列)
言語 (アルファベットを組み合わせてできる文字列の集合)

アルファベット

記号によって構成される空ではない有限集合の事. Σで表されます.

ex.

Σ = {0, 1} // 二進アルファベット
Σ = {a, b, ... , z} // すべての小文字の集合
Σ = {x | xは全アスキー記号の集合}

文字列

任意のアルファベットから選ばれた記号を並べた有限の列の事. 語とも. ωで表します.

ex.二進アルファベットの文字列

0
01011
111101111

アルファベットの中に入っている任意の記号を組み合わせてできた物ですね.

空列( 0個の記号からなる記号列)も, もちろんありです. εで表します.
プログラマーなら, ""で伝わりますかね?

以下補足.

列の長さ

列の長さといわれると, 直感的には文字の記号の数ですが, 厳密にいうと"記号の位置の数"の事を指しています.
イメージするなら, 配列. length()は, 確かに要素の数を返してくれるけれど, 正確には用意されてるセルの数だよね.

文字列の長さは一般的には|ω|と表せます.

ex.

|101| = 3
|ε| = 0

アルファベットのべき乗

あるアルファベットΣに対して作ることが可能な, 長さkの文字列全ての集合を, $Σ^k$で表します.

ex. Σ = {0, 1}の時

$Σ^0$ = {ε} 　　//　c.f. 任意のアルファベットΣに対して k=0の列はεだけ.
$Σ^1$ = {0, 1}
$Σ^2$ = {00, 01, 10, 11}
$Σ^3$ = {000, 001, 010, 011, 100, 101, 110, 111}

ここで気を付けておくべきポイントは, $Σ$と$Σ^1$で, どちらも同じ{0, 1}ではありますが, 示しているものが記号と記号列の点において注意をしなければなりません.

また, $Σ^*$で, そのアルファベットで表すことが可能な全ての文字列の集合を表せ, $Σ^*$から空列εを外した物を$Σ^+$で表します. Unixとかのワイルドカードのイメージです

厳密には

$Σ^* = Σ^0 \cup Σ^1 \cup Σ^2 \cup ...$
$Σ^+ = Σ^1 \cup Σ^2 \cup ...$
$Σ^* = Σ^+ \cup Σ^0$(={ε}) という関係です.

列の連接

記号列の結合です. x, yっていう列があったときに, xのコピーの後にyのコピーをつないでできる列をxyで表し, この操作の事を連接といいます.

例えば,

|x| = i, |y| = j
$x = a_1a_2...a_i$, $y = b_1b_2...b_j$

の時, xとyを連接させると

|xy| = i+j, $xy= a_1...a_ib_1...b_j$

c.f. 基本, 記号はアルファベットの前の方の小文字, 列はw, x, y, zを使うのが慣習です.

また列のn乗はコピーの繰り返しの回数を表します.

例えば, $x^3$は
$x^3 = a_1a_2...a_ia_1a_2...a_ia_1a_2...a_i$
$|x^3| = 3|x|$
となります.

余談ですが, この連接において, εは
εω = ωε = ω
が成立するので, 単位元に当たります.

言語

$Σ^*$に存在する列を組み合わせてできる集合を言語といいます.
直感的に理解をするのであれば, 文字列の集合が言語で, アルファベット -> 英単語 -> 言語の関係がイメージしやすいかと思います.

つまり, Σがアルファベットで, $L \subseteq Σ^*$ならばLはΣ上の言語ということが言えます.

また, アルファベットの組み合わせである文字列は使わないアルファベットがあってもよいことから, LはΣはもちろんですが, Σを含む任意のアルファベット上の言語にもなりえます.

ex. 二進アルファベットにおける言語

$n \geq 0$の時, n個の0の後にn個の1が並んだ列からなる言語: {ε, 01, 0011, 000111....}
0と1が同じ数だけ含まれている列の集合: {01,0101, 111000, 10001...}
素数を表す二進数の集合: {10, 11, 101, 111, 1011...}

どの言語も$Σ*$から抜き出された列の集合であることが分かると思います.

一応言語の書き方は集合と同じのため, 上記のような要素を書き下す方法もありますが,
{ω | ωはn個の0の後にn個の1が並んだ列からなる列の集合}と書いてしまっても問題ありません.
また, 列のn乗の書き方を使い,
{$0^n1^n | n \geq 0 $}と表すことも可能です.

また任意のアルファベットΣに対して以下の事が言えます.

$Σ^*$は言語に含まれる
空集合φも言語に含まれる
空列だけからなる言語{ε}も言語に含まれる.

似てますが, φはなにも含まない言語ですが, {ε}は一つだけ列を含んでいます.

ポイントとして, アルファベットは有限である必要がありますが, 組み合わせ無限大の文字列を含む言語は無限個の文字列を含んでいてもかまいません.

さて, ここで先ほどのオーマトン理論における"問題"というのを見直してみましょう.

ΣがアルファベットでLがΣ上の言語であるとき, 問題Lとは,
与えられた$Σ^*$の中の文字列ωについて, ωがLの中にあるか否かを決定せよ.

わかるようになったでしょうか. つまるところ, ある文字列ωが言語Lの中に含まれるのかという問題を問題Lと呼んでいます.

言語自体がどういった文字列を含むものかを定義しているので, 実際, 言語を定めるという行為は, 問題を解くという行為と全く同じことを指しているのが分かると思います.

実際に世の中一般的な問題をこの帰結問題にしてみるのをやってみましょう.

素数判定の問題の場合与えられた数が素数であるかの判定は,
二進アルファベットΣにおける言語, $L_p$ = {ω | ωは素数}に, 任意の二進アルファベットの文字列yが含まれるかどうかの判定

コンパイラのパーサーのような, 与えられたUnicode文字列が正しい文法か否かも
Σ = {ω | ωはUnicode文字列}における言語, $L_c$ = { y | yはプログラム言語の集合}に任意のUnicode文字列, zが含まれるか同課の判定

という形で落とし込むことができます.
一見, この言いかえはただ単に判定をしているだけで, 実際に例えば素数の値を求めたり, コンパイラからオブジェクトコードを吐き出すような物を欲しいのに, 決定問題(できるかどうか, 正しいかどうかとかの問題)にランクダウンしたように見えるかもしれません.

しかしこの言いかえは非常に興味深いもので, この言いかえによって何が幸せになるかというと, 任意の問題の計算量の下限を証明することができるのです.

はい/いいえをこたえるという言語型の問題は, 実際に問題を解けという問題と"同程度に難しい"⁵事が分かっていて, 非常に計算理論にて重要な手段として使われています.

予備知識の共有をしただけですが, 分量的な面で当記事はこの辺で占めたいと思います.
次の記事では, 有限オートマトンの説明をぼちぼちしていこうと思います.

このようなのんびりとしたノリで今後もぼちぼち解説をしていこうとおもいますが, 自分でできるように資料をいくつか紹介しておきますので合わせて確認してみてください. ⁶, ⁷, ⁸, ⁹, ¹⁰