有限オートマトンがPrologで2行で書けてワロタ

記号処理の授業でProlog勉強中。いろいろわかってきて面白くなってきたが、特に、Prolog処理系の探索機能の便利さに感動。これを使えば、有限オートマトンの文字列受理機構の部分がたった2行で書けるのにはワロタ。簡単な記号処理とかなら、Prologを使うというのもいいのかもしれないなあ。

今頃Prologを勉強して感動って遅れすぎだろとか言うなよ! 絶対言うなよ!

via Prologプログラミング: 言語処理 適宜改訂。

入力文字列の受理・非受理を判定する部分(acceptor.pl)。

fa(Q, [], Q).
fa(Q_S, [A | S], Q_F) :- delta(Q_S, A, Q), fa(Q, S, Q_F).

扱う有限オートマトンのデータ(fa_data1.pl)。初期状態はq0で、受理状態はq3のみとする。

delta(q0, a, q1).
delta(q1, a, q1).
delta(q1, b, q1).
delta(q1, a, q2).
delta(q2, b, q3).

fa_data1.plが表す有限オートマトン(by Graphviz)。

実行例(on gprolog 1.3.0)。

| ?- fa(q0, [a, a, b], q3).

true ? ;

no
| ?- fa(q0, [a, b, a], q3).

no
| ?- fa(q0, [a, b], q3).   

no
| ?- fa(q0, [b, a, b], q3).

no

| ?- fa(q0, [a, b, b, b, a, b], q3).

true ? ;

no
| ?-