5

我一直在通过Learn Prolog Now 取得进展！作为自学，现在正在学习定从句语法。我在实践课程的一项任务中遇到了一些困难。任务内容如下：

形式语言 a n b 2m c 2m d n由以下形式的所有字符串组成：一个完整​​的a s 块，后跟一个完整的b s 块，然后是一个完整的c s 块，然后是一个完整的d s块，使得a和d块的长度完全相同，并且c和d块的长度也完全相同，并且分别由偶数个c s 和d s 组成。例如，ε、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 dn 。_ 以下是我可以生成 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

@Timothy，您的答案有效，但会产生重复项：

?- 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：

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 回答