prüfen, ob ein String in einer Sprache enthalten ist (Prolog)

Question

Dies ist die CFG ist:

S -> T | V 
T -> UU 
U -> aUb | ab 
V -> aVb | aWb 
W -> bWa | ba 

so wird diese in irgendeiner Form annehmen:

{a^n b^n a^m b^m | n,m >= 1} U {a^n b^m a^m b^n | n,m >= 1} 

Und hier ist der Code, den ich bin arbeiten mit:

in_lang([]). 
in_lang(L) :- 
    mapS(L), !. 

mapS(L) :- 
    mapT(L) ; mapV(L),!. 

mapT(L) :- 
    append(L1, mapU(L), L), mapU(L1), !. 

mapU([a|T]) :- 
    ((append(L1,[b],T), mapU(L1)) ; (T = b)),!. 

mapV([a|T]) :- 
    ((append(L1,[b],T), mapV(L1)) ; 
    (append(L1,[b],T), mapW(L1))), 
    !. 

mapW([b|T]) :- 
    ((append(L1,[a],T), mapW(L1)) ; 
    (T = a)), 
    !. 

Wie jetzt aus, das für die folgenden drei Saiten falsch zurückgibt:

[a,a,b,b,a,b] // this should be true 
[a,a,a,b,b,a,a,b,b,b] // this should be true as well 
[a,a,a,b,b,a,b,b,b] // this one IS false 

Jede Hilfe oder Einsicht würde sehr geschätzt werden, ich bin nicht allzu vertraut mit Prolog, so dass das Debuggen von mir selbst eine Herausforderung war.

Answer 1

Zuerst beachten Sie, dass dieser Code nicht sinnvoll:

... append(L1, mapU(L), L) ... 

In Prolog gibt es Prädikate nicht funktioniert ...

A CFG Produktionsregel (ein nicht-Terminal) sollte eine Anzahl von Token "essen", und in Prolog bedeutet dies, dass Sie mindestens 2 Argumente benötigen: die Eingabe-Token-Liste und was nach einer Produktion übrig bleibt, hat den relevanten Teil der Eingabe erfolgreich abgeglichen.

Das heißt, append/3 nicht erforderlich ist: gerade Musteranpassung durch Vereinigung Bediener durchgeführt (=)/2

mapS(L1, L) :- mapT(L1,L) ; mapV(L1,L). 
mapT(L1, L) :- mapU(L1,L2), mapU(L2,L). 
mapU(L1, L) :- L1=[a|L2], mapU(L2,L3), L3=[b|L] ; L1=[a,b|L]. 
... complete the translation 

und dann nennen:

?- mapS([a,a,b,b,a,b],R). 
R = [] ; 
false. 

R = [] bedeutet die gesamte Reihenfolge wurde angepasst ...

Answer 2

In der Definition von mapT versuchen Sie, den "Rückgabewert" mapU als Argument für append zu verwenden. Aber mapU ist ein Prädikat und Prädikate haben keine Rückgabewerte.

Stattdessen schreibt man normalerweise ein Prädikat mit einer ungebundenen Variablen, die das Prädikat an den gewünschten "Rückgabewert" bindet; Nachdem das Predciate bewiesen wurde, kann die jetzt gebundene Variable in nachfolgenden Prädikaten verwendet werden.

Answer 3

Verwenden Sie einfach eine dcg! Und library(double_quotes).

:- set_prolog_flag(double_quotes, chars). 

s --> t | v. 
t --> u, u. 
u --> "a",u,"b" | "ab". 
v --> "a",v,"b" | "a",w,"b". 
w --> "b",w,"a" | "ba". 

| ?- use_module(library(double_quotes)). 

| ?- length(L,N), phrase(s, L). 
L = "abab", N = 4 ? ; 
L = "abab", N = 4 ? ; 
L = "aabbab", N = 6 ? ; 
L = "abaabb", N = 6 ? ; 
L = "aababb", N = 6 ? ; 
L = "abbaab", N = 6 ? ; 
L = "aaabbbab", N = 8 ? ; 
L = "aabbaabb", N = 8 ? ; 
L = "abaaabbb", N = 8 ? ; 
L = "aaababbb", N = 8 ? ...