Reconnaissance du langage A^n B^n dans Prolog sans arithmétique

Question

Comment reconnaître le langage A^n B^n dans Prolog sans arithmétique et pour tout A, B où A! = B?

Avec connu A = A et B = b on pourrait écrire

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

Pour tout A et BI Pensais d'une solution en commençant par

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 

de sorte que les premiers éléments sont d'autant même chose, mais je ne vois pas une manière élégante de vérifier si tous les éléments dans le reste de la liste sont les mêmes et différents que les éléments sur le devant.

Je pourrais vérifier si le reste est aussi long que la liste stockée et ensuite s'il ne comprend que les éléments de second type mais je crois que je suis trop compliqué et qu'il existe une solution courte et simple.

Answer 1

Edit: retour à la solution d'origine, et de s'y tenir:

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

Il est itérative, il ne crée pas le choix des points, il est évident, et il est correct, si tous les éléments du liste sont moulues.

Answer 2

je pense qu'il est plus simple que cela:

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

EDIT: Ceci est facilement généralisable à littéraux arbitraires.

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

EDIT: après Will Ness noter que ça mis sur écoute: ce que je voulais dire était

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. 

équivalent à

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

Utilisez une grammaire clause définie.

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

Démo:

?- phrase(s(1, 2), X). 
X = [] ; 
X = [1, 2] ; 
X = [1, 1, 2, 2] ; 
X = [1, 1, 1, 2, 2, 2] . 

Answer 5

Il est fréquent que les variables DCG nues sont remis en forme comme phrase/3 lors de la traduction. Alors que l'on peut mettre en œuvre A^n B^n non seulement pour quand A et B sont des terminaux, mais aussi lorsque A et B sont des objectifs DCG arbitraires.

Voici le code pour que:

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

Ici, on voit la traduction qui se fait par SWI-Prolog. Comme on peut le voir les variables nues ont été converties à PHRASE/3 buts:

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

Voici une série d'échantillons, pour les terminaux A et 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 . 

Voici une série d'échantillons, pour certains objectifs DCG A et 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