无需算术即可识别Prolog中的A ^ n B ^ n语言 [英] Recognize A^n B^n language in Prolog with no arithmetics

问题描述

如何在Prolog中不使用算术以及对于A！= B的任何A，B来识别A ^ n B ^ n语言?

How to recognize A^n B^n language in Prolog without arithmetics and for any A, B where A != B?

有了已知的A = a和B = b，我们可以写

With known A = a and B = b we could write

% 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和B，我都在考虑从...开始的解决方案

For any A and B I was thinking of a solution starting with

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

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

so that the first elements are all the same, but than I don't see an elegant way of checking whether all elements in the rest of the list are the same and different than the elemenets in the front.

我可以检查其余部分是否与存储列表一样长，然后检查它是否仅由第二类元素组成，但是我认为问题过于复杂，并且存在一个简短的解决方案.

I could check whether the rest is as long as the stored list and then whether it only consists of the second type elements but I believe I'm overcomplicating the problem and there exists a short and simple solution.

推荐答案

回到原始解决方案，并坚持下去:

back to the original solution, and sticking to it:

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).

这是迭代的，它不会创建选择点，很明显，如果列表中的所有元素都是基础的，这是正确的.

It is iterative, it does not create choice-points, it is obvious, and it is correct, if all elements of the list are ground.

这篇关于无需算术即可识别Prolog中的A ^ n B ^ n语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！