引き続き、アンダースタンディング コンピュテーションを読んでいます。
アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで
- 作者: Tom Stuart,笹田耕一,笹井崇司
- 出版社/メーカー: オライリージャパン
- 発売日: 2014/09/18
- メディア: 大型本
- この商品を含むブログ (11件) を見る
先日はいろんな言語でDFAを書いてみたわけですが、よくよくコードを読み直してみると、Prologのばあいはもっと簡単にDFAを書けることに気がつきました。
というか、Prologのコードは、ほとんどルールそのものだった、というお話。
決定性有限オートマトン: Deterministic Finite Automaton (DFA)
DFAでは、ある状態である入力があったときの遷移先が１つに決定しています。
次のような状態遷移表で表されるDFAを書いてみます。
| 状態＼入力 | a | b |
|---|---|---|
| 1 | 2 | 1 |
| 2 | 2 | 3 |
| 3 | 3 | 3 |
DFAのコード。
rule(1, 0'a, 2). rule(1, 0'b, 1). rule(2, 0'a, 2). rule(2, 0'b, 3). rule(3, 0'a, 3). rule(3, 0'b, 3). dfa(State, [], State). dfa(StartState, [C|CS], LastState) :- rule(StartState, C, NextState), dfa(NextState, CS, LastState). isAccepts(StartState, AcceptStates, String, true) :- dfa(StartState, String, LastState), member(LastState, AcceptStates). isAccepts(_, _, _, false).
DFAをテストするコード。開始状態は 1 、受理状態は 3 です。
test(StartState, AcceptStates, String) :- isAccepts(StartState, AcceptStates, String, Result), format("~s => ~p~n", [String, Result]). main :- test(1, [3], "a"), test(1, [3], "baa"), test(1, [3], "baba").
実行結果。
$ swipl -s dfa.prolog -g 'main, halt' a => false baa => false baba => true
非決定性有限オートマトン: Nondeterministic Finite Automaton (NFA)
NFAでは遷移先が１つに決まりません。そのため、各々の遷移先に対する挙動を考慮しなければなりません。
| 状態＼入力 | a | b |
|---|---|---|
| 1 | 1 | 1 or 2 |
| 2 | 3 | 3 |
| 3 | 4 | 4 |
…なのですが。Prologにはバックトラックというしくみが言語自体に組み込まれています。これによって、複数の遷移先があるばあいでも各々の挙動を網羅することができるようになっています。
ja.wikipedia.org に解説がありますので、詳しくはこちらへ：
NFAのコード。
実際のところ、rule の内容を変更し、名前を dfa から nfa に変えただけで、処理自体は DFA と同じです。
rule(1, 0'a, 1). rule(1, 0'b, 1). rule(1, 0'b, 2). rule(2, 0'a, 3). rule(2, 0'b, 3). rule(3, 0'a, 4). rule(3, 0'b, 4). nfa(State, [], State). nfa(StartState, [C|CS], LastState) :- rule(StartState, C, NextState), nfa(NextState, CS, LastState). isAccepts(StartState, AcceptStates, String, true) :- nfa(StartState, String, LastState), member(LastState, AcceptStates). isAccepts(_, _, _, false).
ちょっと挙動を確認してみます。
$ swipl -s nfa.prolog ?- nfa(1, "b", R). R = 1 ; R = 2 ; false.
swipl -s nfa.prolog でファイルを読み込んでいます。
プロンプトが表示されるので nfa(1, "b", R). と入力します。
実行結果として R = 1 と表示され、一旦入力待ちになります。ここでセミコロンを入力すると別の解を求めるため実行を再開します。
別の結果として R = 2 と表示されます。これらはそれぞれ、状態1のときに入力Bがあったばあいの結果（遷移先の状態）の状態1と状態2に対応します。
２つ目の解を表示したあと再び入力待ちになっているのでセミコロンを入力すると、これ以上解がないので false. を表示して処理を終了します。
NFAをテストするコード。開始状態は 1 、受理状態は 4 です。
test(StartState, AcceptStates, String) :- isAccepts(StartState, AcceptStates, String, Result), format("~s => ~p~n", [String, Result]). main :- test(1, [4], "bab"), test(1, [4], "bbbbb"), test(1, [4], "bbabb").
実行結果。
$ swipl -s nfa.prolog -g 'main, halt' bab => true bbbbb => true bbabb => false
自由移動のある NFA
入力がなくても自発的に遷移する自由移動があるばあいを考えます。
下記の状態遷移表ではεで書いた列が自由移動です。遷移先が - となっている部分は、そのような遷移のルールがないことを表しています。
| 状態＼入力 | a | ε |
|---|---|---|
| 1 | - | 2 or 4 |
| 2 | 3 | - |
| 3 | 2 | - |
| 4 | 5 | - |
| 5 | 6 | - |
| 6 | 4 | - |
状態1は自由移動で、つまり入力がなくても自発的に、状態2か状態4に遷移します。
自由移動のあるNFAのコード。
入力を必要としない rule/2 と、 rule/2 を利用して入力をとらずに遷移するコードを追加しています。
rule(1, 2). rule(1, 4). rule(2, 0'a, 3). rule(3, 0'a, 2). rule(4, 0'a, 5). rule(5, 0'a, 6). rule(6, 0'a, 4). nfa(State, [], State). nfa(StartState, CS, LastState) :- rule(StartState, NextState), nfa(NextState, CS, LastState). nfa(StartState, [C|CS], LastState) :- rule(StartState, C, NextState), nfa(NextState, CS, LastState). isAccepts(StartState, AcceptStates, String, true) :- nfa(StartState, String, LastState), member(LastState, AcceptStates). isAccepts(_, _, _, false).
ちょっと挙動を確認してみます。
?- nfa(1, "", R). R = 1 ; R = 2 ; R = 4 ; false.
状態1のばあい、入力がなくても状態2か状態4に遷移することがわかります。遷移せず状態1のままという場合もあるので、このばあいは状態1,2,4のいずれかが取りうる値となります。
自由移動のあるNFAをテストするコード。開始状態は 1 、受理状態は 2 か 4 です。
test(StartState, AcceptStates, String) :- isAccepts(StartState, AcceptStates, String, Result), format("~s => ~p~n", [String, Result]). main :- test(1, [2, 4], "aa"), test(1, [2, 4], "aaa"), test(1, [2, 4], "aaaa"), test(1, [2, 4], "aaaaa").
実行結果。
$ swipl -s nfa.prolog -g 'main, halt' aa => true aaa => true aaaa => true aaaaa => false
