6

この形式に一致するすべてのリストを認識するDCGを構築しようとしています：a^n b^2m c^2m d^n。
私は次のルールを書きました：
s --> [].
s --> ad.
ad --> a, ad, d.
ad --> bc.
bc --> b, b, bc, c, c.
bc --> [].
a --> [a].
b --> [b].
c --> [c].
d --> [d].

リストのように、これらの仕様で文字列を評価しようとすると、[a,b,b,c,c,d]機能します。しかし、phrase(s, X)この文法によって返される可能性のあるすべての文字列を確認できるようにクエリを評価しようとすると、無限にループします。

DCGの構築方法に何か問題がありますか？

4

4 に答える 4

6

反復的な深化により、文字列を公平に列挙できます。

?- length(Ls, _), phrase(s, Ls).
Ls = [] ;
Ls = [] ;
Ls = [a, d] ;
Ls = [a, a, d, d] ;
Ls = [b, b, c, c] ;
etc.
于 2011-01-04T17:01:54.850 に答える
0

この質問のプロローグ部分が表示されません。答えは、この文法をどのように実装したかによって大きく異なります。

私の最善の推測は、ルールの順序を逆にして、終了ルールを最初に適用することです。

于 2011-01-04T15:21:51.030 に答える
0

無限の解があるにもかかわらず、解を制限するのを助ける方法としてこれを書きました。しかし、最初に短い結果が得られるようにルールを再構成する方法があることに気付きました。

beforeを満たそうとするad --> a, ad, d.前に評価されるから です。前に置きます。andルールについても同様です。ad --> bc.ad --> a, ad, a.ad --> bc.ad --> bc.ad --> a, ad, a.bc --> b, b, bc, c, c.bc --> [].

アリアンが指摘したように、終了ルールを最初に適用すると、より短いソリューションが最初に見つかるようになります。

[]また、 s と s -> ad -> bc -> [] に は 2 つの解決策があることも指摘したいと思いs --> [].ます。これは冗長なので削除します。

全体として、私はこの解決策を試します：

s --> ad.
a --> [a].
b --> [b].
c --> [c].
d --> [d].
ad --> bc.
bc --> [].
ad --> a, ad, d.
bc --> b, b, bc, c, c.

元の投稿:

数え方を調べる必要がありました (prolog を行ってからしばらく経ちました) しかし、無限の数があり、prolog はすべての解を見つけようとするため、検索が停止することはありません。その前にフローまたはいくつかのエラー:)。

結果の数を制限する 1 つの方法は、ソリューションのサイズを制限することです。

 phrase(s, X), length(X, 4).

ちょうど 4 つの値を持つすべてのソリューションを取得します。

X = [a, a, d, d]
X = [b, b, c, c]

6 に増やすと、次のようになります。

X = [a, a, a, d, d, d]
X = [a, b, b, c, c, d]

または範囲を使用します。

 phrase(s, X), length(X, Y), Y >= 4 , Y < 10, Y != 6.
于 2011-02-02T02:31:51.927 に答える