Prologでオートマトン定義

授業でオートマトンの講義を受けていて、Prologでやると綺麗に書けるなぁ
とおもう場面が多々あったのでPrologで書いてみました。
とりあえず

0が三つ連続して出現する文字列を受理するオートマトン

single([_]).

butlast(Xs, []) :- single(Xs).
butlast([X | Xs], [X | Ys]) :- butlast(Xs, Ys).

last([],[]).
last([Xs],Xs).
last([_ | Xs], Ys) :- last(Xs, Ys).

d(q0,0,q1).
d(q0,1,q0).
d(q1,0,q2).
d(q1,1,q0).
d(q2,0,q3).
d(q2,1,q0).

d(q3,1,q3).
d(q3,0,q3).

dh(FROM,[],FROM).

dh(FROM,W,TO) :- 
        butlast(W,X), 
        last(W,A),
        dh(FROM, X, NEXT),
        d(NEXT,A,TO).

ちょっとリストを最後の1つと先頭に分けるという処理でてまどってますが..
dはδ関数の定義です。dhは指定したリストを入力したときの状態遷移を一気におこなう関数ですδ^ (delta-hat)の略です。
初期状態はq0, 終了状態はq3です。
図にするとこんなん
f:id:Pocket7878_dev:20130423193117p:plain
これで...

?- dh(q0,[0,0,1],X).
X = q0 ;
false.

?- dh(q0,[0,0,0],X).
X = q3 ;
false.

?- dh(q0,[0,0,0,1],X).
X = q3 ;
false.

やらとテストできます。終了状態かどうかの定義をつけてacceptとかの定義をしたらさらにスッキリするかもしれませんね。

それよりもおもしろいと感じるのは、こんな質問をする事が可能だという事です。

?- dh(q0,[0,Y,0,1],q3).
Y = 0 ;
false.

?- dh(q0,[0,0,0,Y],q3).
Y = 1 ;
Y = 0 ;
false.

?- dh(q0,[X,0,0,Y],q3).
X = 0,
Y = 1 ;
X = Y, Y = 0 ;
X = 1,
Y = 0 ;
false.

こんな風に、最終状態に到達するためには、XやYがどんな値だったら良いのだろうか？という質問をする事ができます。最後の質問への回答などはなかなかおもしろいですね。きちんと

[0,0,0,1]
[0,0,0,0]
[1,0,0,0]

という3種類の列が可能である事が出力されています。

Let's write β

プログラミング中にできたことか、思ったこととか

Prologでオートマトン定義