3

如何在没有算术的情况下识别 Prolog 中的 A^n B^n 语言以及对于 A != B 的任何 A、B？

已知 A = a 和 B = b 我们可以写

% For each 'a' save 'b' in a list, then check 
% whether constructed list is equal to the rest of input list

anbn(L) :- anbn(L, []). 

anbn(L, L). 

anbn([a|L],A) :- anbn(L, [b|A]).

对于任何 A 和 BI 都在考虑从

anbn(L) :- anbn(L, []).

anbn([H|L],[]) :- anbn(L,[H]). % save an element

anbn([H|L], [H|A]) :- anbn(L, [H,H|A]). % make sure front elements are the same

所以第一个元素都是相同的，但是我没有看到一种优雅的方法来检查列表其余部分中的所有元素是否与前面的元素相同和不同。

我可以检查其余的是否与存储的列表一样长，然后检查它是否仅包含第二种类型的元素，但我相信我使问题过于复杂，并且存在一个简短而简单的解决方案。

4

5 回答 5

8

使用明确的从句语法。

s(_, _) --> [].
s(A, B) --> [A], s(A, B), [B].

演示：

?- phrase(s(1, 2), X).
X = [] ;
X = [1, 2] ;
X = [1, 1, 2, 2] ;
X = [1, 1, 1, 2, 2, 2] .
于 2013-05-07T12:15:17.320 回答
2

编辑：回到原来的解决方案，并坚持下去：

anbn(List) :- List = [] -> true; List = [A|Rest], a(Rest, A, 0).

a([A|Rest], A, N) :- !, a(Rest, A, s(N)).
a([B|Rest], _, N) :- b(Rest, B, N).

b([B|Rest], B, s(N)) :- b(Rest, B, N).
b([], _, 0).

它是迭代的，它不会创建选择点，很明显，而且如果列表的所有元素都是接地的，它是正确的。

于 2013-05-07T11:32:53.020 回答
2

对于 DCG，裸变量在翻译过程中被重新包装为短语/3 是很常见的。因此，不仅当 A 和 B 是终端时，而且当 A 和 B 是任意 DCG 目标时，都可以实现 A^n B^n。

这是代码：

 s(_,_) --> [].
 s(A,B) --> A, s(A,B), B.

这里可以看到由 SWI-Prolog 完成的翻译。可以看到，裸变量已转换为短语/3 个目标：

 ?- listing.
 s(_, _, A, A).
 s(A, C, B, F) :-
    phrase(A, B, D),
    s(A, C, D, E),
    phrase(C, E, F).

以下是终端 A 和 B 的示例运行：

 ?- phrase(s("alfa","beta"),X), atom_codes(Y,X).
 X = [],
 Y = '' ;
 X = [97, 108, 102, 97, 98, 101, 116, 97],
 Y = alfabeta ;
 X = [97, 108, 102, 97, 97, 108, 102, 97, 98|...],
 Y = alfaalfabetabeta ;
 X = [97, 108, 102, 97, 97, 108, 102, 97, 97|...],
 Y = alfaalfaalfabetabetabeta .

这是一个示例运行，对于一些 DCG 目标作为 A 和 B：

  bit --> "0".
  bit --> "1".

  ?- length(L,8), phrase(s(("(",bit),(bit,")")),L), atom_codes(R,L).
  L = [40, 48, 40, 48, 48, 41, 48, 41],
  R = '(0(00)0)' ;
  L = [40, 48, 40, 48, 48, 41, 49, 41],
  R = '(0(00)1)' ;
  L = [40, 48, 40, 48, 49, 41, 48, 41],
  R = '(0(01)0)' ;
  Etc..

再见

于 2013-05-15T21:02:55.537 回答
0

我认为它比这更简单：

anbn(L) :- append(As, Bs, L), maplist(ab, As, Bs).
ab(a, b).

编辑：这很容易推广到任意文字。

anbn(L) :- L = [A|_], append(As, Bs, L), maplist(ab(A), As, Bs).
ab(A, A, B) :- A \== B.

编辑： Will Ness 注意到这是错误的：我的意思是

anbn(L) :- append([A|As], [B|Bs], L), A \= B, maplist(ab(A, B), As, Bs).
ab(A, B, A, B).
于 2013-05-07T11:33:01.890 回答
0 
anbn( [] ) :- !.
anbn( L ) :- L=[A|_], copy_half( L,L, Z,Z, A,_V). % Z is second half
copy_half( [A|B], [_,_|C], [V|D], Z, A,V) :- !, copy_half( B,C, D,Z, A,V).
copy_half( Z,     [],      [],    Z, A,V) :- A \== V.

相当于

anbn_verboten(L):- L = [] ;
  length(L,N), N2 is N div 2, length(X,N2), length(Y,N2), append(X,Y,L), 
  L=[P|_], Y=[Q|_], P \= Q.`.
于 2013-05-07T12:13:30.690 回答