コンパイラの tokenizer のための Finite Automaton 入門
Menu Menu
C で書く Automaton
Automaton は、状態遷移機械とも呼ばれる。状態は、初期状態と、終状態、そして、いくつかの有限個の中間状態からなる。
入力は、ここでは文字列、つまり、コンパイラの入力としよう。
一つ一つの入力は、文字となる。文字の集合を遷移条件と言う。
ある状態で、遷移条件にあった文字が来たら、次の状態に移行する。つまり、
＊ 状態毎に、遷移条件と次の状態の組みがある。
最初は初期状態から初めて、終状態に遷移したら、その文字列は Automaton に受け入れられたと言う。
それ以外の場合に、文字列の終わりに到達したら、その文字列は受け入れられなかったことになる。
Automaton に受け入れられた時には、空かもしれない残りの文字列があることになる。
Automaton の実装
一番簡単なのは、switch 文を使う。
状態 = 初期状態;
while( 文字列が空でない ) {
switch (状態) {
case 状態1 :
if ( 文字列の集合判定 ) 状態 = 次の状態;
if ( 文字列の集合判定 ) 状態 = 次の状態;
if ( 文字列の集合判定 ) 状態 = 次の状態;
break;
...
case 状態2 :
case 終状態 :
return Accept;
}
}
return Reject;
これは、特に決定性 Finite Automaton (DFA) と呼ばれる。
OOLの場合は State Patternを使う。
数値を受け入れる Automaton
(1) 自然数(0を含む) を受け入れる Automaton を記述せよ(2) 整数(符号-を含む) を受け入れる Automaton を記述せよ
(3) 固定小数点(.を含む) を受け入れる Automaton を記述せよ
(4) 浮動小数点(指数と.を含む) を受け入れる Automaton を記述せよ (option)
正規表現
文字の集合 * その繰り返し その結合 | 複数の正規表現の選択これで表現できるものを正規表現という。Unix の shell は正規表現を持っている。
正規表現はDFA で実装でき、DFA は正規表現で表すことができる。
(1)-(4) を、正規表現で表してみよ。
DFA では判定することのできない文字列
カッコの対応をDFAで判定することはできない。それは何故か、説明せよ。
Push Down Automaton
状態の Stack を一つ持つ Automaton の拡張。
push(状態);
状態= pop();
を使うことができる。状態ではなく、状態変数を使っても良い。
stack を一つ導入して、カッコの対応を判定する Push Down Automaton を作成せよ。
Context Free Grammer
Context Free Grammer は Push Down Automaton に変換できる。(Recursive decent)
Turing Machine
特に Stack を二つ持つ Automaton を決定性 Turing Machine と言うStack 二つを、テープとヘッドで表したものを普通は使う。
非決定性 Automaton
遷移条件が、互いに排他でない場合、if 文のどれかが成功すれば良いとする。その次の状態でも同じ。これは、条件が重なっている時には、それをすべて並列に探すことを意味する。
これを 非決定性 Automaton (NFA) と言う。
(5) 自明にDFAと等しくない NFA を考えよ。
NFA を実行するには、どうすればよいか?
すべての重複した状態を調べれば良い。しかし、 深さ優先探索ではダメ、何故か?
幅優先探索を使えば良い。
(6) NFA の幅優先探索を実装せよ (option)
NFA から DFA への変換
Subset construciton によって、NFA から DFA へ変換することができる。(7) (5) を DFA に変換して実装せよ。
(8) (6) と (7) が同等であることを調べよ。(option)
したがって、NFA は DFA よりも強力なわけではない。
非決定 Turing Machine
DFA の代わりに NFA を使った Stack を二つ持つ Turing machine 。非決定 Turing Machine は、決定性 Turing Machine を使って simulation することができる。
万能 Turing machine
任意のTuring machine を、 その入力とTuring Machineの記述を入力として、Simulation する Turing machine
Turing machine の停止性
決定性 Turing machine が与えれた入力に対して停止するかどうかを判定する決定性 Turing machine は存在しない。万能 Turing machine を使って、これを証明することができる。
計算量
計算量は、入力の長さに対して決まる。例えば、時間計算量
長さnに比例する時間 O(n)
長さnの自乗する時間 O(n^2)
長さnのにlogする時間 O(log(n)) (n以下になるの?)
長さnのにn* logn の時間 O(n*log(n))
領域計算量
計算に必要なメモリ量 (二つのstack の長さの和)
P
決定性Turing machine を使って、かかる時間が O(p(n))。p(n) は、多項式時間 n^m (m は 1より大きい整数)。
(9) P な問題を示して、実装し、実測せよ (option)
NP
非決定性Turing machine を使って、かかる時間が O(p(n))。p(n) は、多項式時間 n^m (m は 1より大きい整数)。非決定性Turing machine は、決定性Turing machineで simulation することができる。しかし、その時間計算量はO(exp(n)) である。
NFA は DFA で simulation でき、計算時間は変わらない。しかし、非決定性 Turing machine を決定性 Turing machine で simulation するには、複数本の stack が必要となるので、自明な変換は存在しない。
従って、 NP は現状の知られている実装は O(exp(n)) である。しかし、O(exp(n)) だとは証明されていない。
命題論理式の充足問題は NP であることが知られている。
(10) 非決定性Turing machine の、決定性Turing machineによる simulatior を作成せよ (option) ヒント Turing machine の1 step を実行するオブジェクトを作り、それを breadth first に実行する scheduer を作る。
EXP
決定性Turing machine を使って、かかる時間が O(exp(n))。p(n) は、指数時間 m^n (m は 1より大きい整数)。(11) EXP な問題を示して、実装し、実測せよ (option) NP な問題で構わない。
P space
決定性Turing machine を使って、領域計算量が O(p(n))。P space は NP、P を含む。新に含むかどうかはわかっていない。(12) P space な問題を示して、実装し、実測せよ (option)
量化記号を持つ命題論理式の充足問題は P space であることが知られている。
co NP
NP な判定されない部分。(13) co NP な問題を示して、実装し、実測せよ (option)
決定性Turing machine は止まるとは限らないので、判定されない部分は、NP になるとは限らない。
命題論理式の非充足問題は co NP であることが知られている。
計算量の問題
わかっっている問題P と NP が P-Space の部分集合であることはわかっている。
P-Space が EXP の部分集合であることはわかっている。
わかってない問題
P=NP P=co P NP=co NP NP=P space
オラクル (option)