次の Prolog プログラムは、非決定論的オートマトンをシミュレートします。
final(s3).
trans(s1,a,s2).
trans(s1,b,s1).
trans(s2,b,s3).
trans(s3,b,s4).
silent(s2,s4).
silent(s3,s1).
accepts(State,[]) :- final(State).
accepts(State, [X|Rest]) :- trans(State,X,State1),
accepts(Stat1,Rest).
accepts(State, Rest) :- silent(State, State1),
accepts(State1, Rest).
わかりました、3 種類の事実があります。
最初のものは、 s3が最終状態(受容の状態) であると私に言います。事実の 2 番目の類型は、文字列の文字を読み取るオートマトンの遷移を指定します。
例: 状態 s1 にいて、文字 a が読み取られると、状態 s2 に移行できます。
3 つ目は null 遷移を指定します。これは、入力文字を必要としない状態から別の状態への任意の遷移です。
例えば：
silent(s2,s4)
オートマトンが何も読み取らずに s2 から s4 に任意に渡せるように指定します。
これで、ある状態から別の状態に移行する方法と、それが受け入れ状態かどうかを指定するルールができました。
最初のルールは次のとおりです。
accepts(State,[]) :- final(State).
空の文字列 []は、この状態が最終状態である場合、State から受け入れられます。
2 番目のルールは次のとおりです。
accepts(State, [X|Rest]) :- trans(State,X,State1),
accepts(State1,Rest).
つまり、文字列 it は空ではなく、この文字列は現在の状態 State から受け入れられます。文字列の最初の記号 X を読み取った場合、オートマトンは状態 State1 に渡すことができ、文字列の残りの部分は State1 から受け入れられます。
3 番目のルールは次のとおりです。
accepts(State, Rest) :- silent(State, State1),
accepts(State1, Rest).
オートマトンが現在の状態 State から別の状態 State1 に静かに移動でき、状態 State1 が入力文字列全体を受け入れることができる場合、文字列は State から受け入れられます。
したがって、Prolog シェルで次のステートメントを実行するとします。
accepts(s1,[a,a,a,b]).
応答は真です
しかし、正確にはどういう意味ですか？
これは、s1 状態が [a,a,a,b] 文字列を受け入れることを意味します。これは、初期状態 s1 から受け入れ状態 s3 に移行するオートマトンの遷移が多数あるためです。
2番目の疑いは、本に示されている例に関連しています。
本でこのクエリを実行し (s1 から最終状態 s3 に至る 3 文字のシーケンスをすべて取得します)、次の出力を取得します。
?- accepts(s1, [X1,X2,X3]).
X1 = a
X2 = a
X3 = b;
X1 = b
X2 = a
X3 = b;
no
これは合理的ですが、Prolog シェルで実行しようとすると、次の出力が得られます。
11 ?- accepts(s1, [X1,X2,X3]).
X1 = X2, X2 = a,
X3 = b ;
X1 = X3, X3 = b,
X2 = a ;
false.
なんで？