Признать язык A^n B^n в Prolog без арифметики

Question

Как распознать язык A^n B^n в Prolog без арифметики и для любых A, B, где A! = B?

С известной А = а и 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]). 

Для любого А и Б. имел в виду решение, начиная с

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 

так, что первые элементы являются все То же самое, но я не вижу элегантного способа проверить, все ли элементы в остальном списке одинаковы и отличаются от элементов впереди.

Я мог бы проверить, осталось ли остальное до тех пор, пока сохраняется список, а затем состоит ли он только из элементов второго типа, но я считаю, что я преувеличиваю проблему, и существует короткое и простое решение.

Answer 1

Edit: вернуться к исходному раствору, и приклеить к нему:

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

Это итеративный, он не создает выбор-точек, то очевидно, и это правильно, если все элементы список.

Answer 2

Я думаю, что это проще, чем:

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

EDIT: Это легко обобщается на произвольные литералов.

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

EDIT: после Вилл Ness отметив, что это прослушивается: то, что я имел в виду

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

Answer 3

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

Answer 4

Используйте определенный раздел грамматики.

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

Answer 5

Это характерно для DCGs, что голые переменные rewrapped как фраза/3 во время перевода. Чтобы можно было реализовать A^n B^n не только тогда, когда A и B являются терминалами, но и , когда A и B являются произвольными целями DCG.

Вот код для этого:

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

Ниже приведен пример выполнения, для терминалов А и В:

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

Bye