prolog - プロローグ: n >= 1 で a^nb^(n+1) 言語を認識する

Question

宿題を自分で考えなければならないことは理解していますが、クラスの誰もそれを理解できないので、助けが必要です。

任意の について、 がの後に が続くリストでp(X) ある場合に真となるような Prolog プログラムを作成します。Xn an+1 bn >= 1

Answer 1

これをPrologでコーディングする方法を覚えていませんが、アイデアは次のとおりです。

ルール1：listsizeが1の場合、要素がBの場合はtrueを返します。

ルール2：listsizeが2の場合、falseを返します。

ルール3：リストの最初の項目がAで、最後の項目がBであるかどうかを確認します。これが当てはまる場合は、要素2の解をlistsize-1に返します。

私があなたの問題を正しく理解していれば、それは完璧なPrologスタイルの解決策になるはずです。

編集：私はこれを完全に忘れました。n=1とn=2の場合を考慮して回答を編集しました。HeathHunnicuttに感謝します。

Answer 2

カウンターを使用して、これまでに見つけたものを追跡する必要があります。を見つけたらb、カウンターに 1 つ追加します。を見つけたら、a1 を引きます。bの数をの数よりも 1 だけ多くしたいので、リスト全体がトラバースされた後のカウンターの最終的な値は 1 になるはずですa。これをコードで記述する方法の例を次に示します。

% When we see an "a" at the head of a list, we decrement the counter.
validList([a|Tail], Counter) :-
  NewCounter is Counter - 1,
  validList(Tail, NewCounter).

% When we see an "b" at the head of a list, we increment the counter.
validList([b|Tail], Counter) :-
  NewCounter is Counter + 1,
  validList(Tail, NewCounter).

% When we have been through the whole list, the counter should be 1.
validList([], 1).

% Shortcut for calling the function with a single parameter.
p(X) :-
  validList(X, 0).

さて、これはあなたが望むほとんどのことをします - それは all のルールにマッチしますがn >= 0、あなたは all に対してそれを望みますn >= 1。典型的な宿題の答えのやり方で、私はあなたが自分自身を追加するために最後のビットを残しました.

Answer 3

ここに私の難解な解決策があります

:-use_module(library(clpfd)).

n(L, N) -->
    [L],
    {N1 #= N-1
    },
    !, n(L, N1).
n(_, 0) --> [], !.

ab -->
    n(a, N),
    {N1 is N + 1
    },
    n(b, N1).

p(X) :- phrase(ab, X).

test :-
    p([b]),
    p([a,b,b]),
    p([a,a,b,b,b]),
    p([a,a,a,b,b,b,b]),
    \+ p([a]),
    \+ p([a,b]),
    \+ p([a,a,b,b]),
    \+ p([a,b,b,c]).

テスト:

 ?- [ab].
% ab compiled 0.00 sec, -36 bytes
true.

 ?- test.
true.