5

Learn Prolog Now!を進めてきました。独学で、定款文法を学んでいます。実践セッションのタスクの 1 つに問題があります。タスクは次のとおりです。

形式言語 a n b 2m c 2m d nは、次の形式のすべての文字列で構成されます: a の切れていないブロックの後にbの切れていないブロックが続き、その後にcの切れていないブロックが続き、その後にdの切れていないブロックが続きます。、aとdのブロックがまったく同じ長さであり、cとdのブロックもまったく同じ長さであり、さらにそれぞれ偶数個のcとdで構成されるようにします。たとえば、ε、abbccd、およびaaabbbbccccdddはすべて a n b 2m c 2m d nに属します。この言語を生成する DCG を書きます。

a n d n、 b 2m c 2m、さらには a n b 2mと c 2m d nを生成するルールを書くことはできますが、これらすべてのルールを a n b 2m c 2mに結合することはできないようですd n . 以下は a n d nと b 2m c 2mを生成できる私のルールです。

s1 --> [].
s1 --> a,s1,d.
a --> [a].
d --> [d].

s2 --> [].
s2 --> c,c,s2,d,d.
c --> [c].
d --> [d].

a n b 2m c 2m d nは本当に CFG ですか? また、レッスンで教えられたことだけを使用して (追加の引数やコードなどを使用せずに) DCG を作成することは可能ですか? もしそうなら、与えられたタスクを解決できるように、これらに参加する方法を教えてもらえますか?

4

3 に答える 3

6

@ティモシー、あなたの答えは機能しますが、重複が生成されます：

?- length(S,_), s(S,[]).
S = [] ;
S = [a, d] ;
S = [a, d] ;            % XXX
S = [b, b, c, c] ;
S = [a, a, d, d] ;
S = [a, a, d, d] ;      % XXX

これは、DCGを残して、1つの句を削除することで修正できます。

s --> x.
s --> a,s,d.

x --> [].
x --> b,b,x,c,c.

% a, b, c, d the same

これにより、以下が生成されます。

?- length(S,_), s(S,[]).
S = [] ;
S = [a, d] ;
S = [b, b, c, c] ;
S = [a, a, d, d] ;
S = [a, b, b, c, c, d] ;
S = [a, a, a, d, d, d] ;
S = [b, b, b, b, c, c, c, c] ;
S = [a, a, b, b, c, c, d, d] ;
S = [a, a, a, a, d, d, d, d] ;
于 2010-06-12T12:04:12.477 に答える
3

私はそれを理解したと思います...

s --> x.
s --> a,d.
s --> a,s,d.

x --> [].
x --> b,b,x,c,c.

a --> [a].
b --> [b].
c --> [c].
d --> [d].

?- s([],[]).
Yes

?- s([a,b,c,c,d],[]).
No

?- s([a,a,a,b,b,c,c,d,d,d],[]).
Yes

解決策を見て、「頭を悩ませたのか」と考えるのはおもしろいです。しかし、それは、特に命令型プログラミングのバックグラウンドから来る論理プログラミングのようなものである場合、何か新しいことを学ぶことの半分の楽しみだと思います。

于 2010-06-10T04:00:26.840 に答える
0

次のようなものはどうですか？

n(L,N) --> n(L,N,0).

n(_,N,N) --> [], !.
n(L,N,K) --> L, {K1 is K + 1}, n(L, N, K1).

abbccd(N,M) -->
    {M1 is 2*M},
    n("a",N),
    n("b",M1),
    n("c",M1),
    n("d",N).

gen :-
    forall((
           between(1,4,N),
        between(1,4,M),
        phrase(abbccd(N,M),S),
        string_to_atom(S,A)
           ),
           writeln(A)).

実行中：

 ?- gen.
abbccd
abbbbccccd
abbbbbbccccccd
abbbbbbbbccccccccd
aabbccdd
aabbbbccccdd
aabbbbbbccccccdd
aabbbbbbbbccccccccdd
aaabbccddd
aaabbbbccccddd
aaabbbbbbccccccddd
aaabbbbbbbbccccccccddd
aaaabbccdddd
aaaabbbbccccdddd
aaaabbbbbbccccccdddd
aaaabbbbbbbbccccccccdddd
true.
于 2010-06-08T13:53:32.017 に答える