Pytanie - język formalny w prologu

Question

Próbuję zbudować DCG, który rozpoznaje wszystkie listy pasujące do tego formularza: a^n b^2m c^2m d^n.
Pisałem się następujące zasady:
s --> [].
s --> ad.
ad --> a, ad, d.
ad --> bc.
bc --> b, b, bc, c, c.
bc --> [].
a --> [a].
b --> [b].
c --> [c].
d --> [d].

Kiedy próbuję ocenić ciąg o tych specyfikacjach, takich jak lista [a,b,b,c,c,d], to działa. Ale kiedy próbuję ocenić zapytanie phrase(s, X), tak że widzę wszystkie możliwe łańcuchy zwracane przez gramatykę, to pętle do nieskończoności.

Czy jest coś złego w sposobie, w jaki zbudowałem DCG?

Answer 1

Można wyliczyć ciągi dość z iteracyjnym pogłębianiem:

?- length(Ls, _), phrase(s, Ls). 
Ls = [] ; 
Ls = [] ; 
Ls = [a, d] ; 
Ls = [a, a, d, d] ; 
Ls = [b, b, c, c] ; 
etc. 

Answer 2

Nie widzę części prologu tego pytania. Odpowiedź bardzo zależy od tego, jak zaimplementowałeś tę gramatykę.

Moim zdaniem można odwrócić kolejność reguł, aby najpierw zastosować reguły kończące.

Answer 3

pisałem to jako sposób, aby pomóc rozwiązań dopuszczalnych, chociaż istnieje nieskończenie wiele rozwiązań. Ale zdałem sobie sprawę, że istnieje sposób na zmianę reguł, aby najpierw uzyskać krótsze wyniki.

Ponieważ ad --> a, ad, d. jest oceniany przed ad --> bc. stara się zaspokoić ad --> a, ad, a. przed ad --> bc.. Wstawię ad --> bc. przed ad --> a, ad, a.. To samo dotyczy reguł bc --> b, b, bc, c, c. i . Zgodnie z tym, co wskazano w arianach, najpierw zastosowane zostaną reguły kończące, które zapewniają, że krótsze rozwiązania zostaną znalezione jako pierwsze.

Chciałbym również zwrócić uwagę, że istnieją dwa rozwiązania dla [] s i s -> ad -> bc -> [] Wyeliminowałbym s --> []., ponieważ jest zbędny.

W sumie chciałbym spróbować tego rozwiązania:

s --> ad. 
a --> [a]. 
b --> [b]. 
c --> [c]. 
d --> [d]. 
ad --> bc. 
bc --> []. 
ad --> a, ad, d. 
bc --> b, b, bc, c, c. 

Original post:

musiałem patrzeć, jak to zrobić liczenia (to było dawno zrobiłem prolog), ale nie są nieskończona liczba, a prolog próbuje znaleźć wszystkie rozwiązania, których nigdy nie przestaje szukać, chociaż jestem pewien, że trafisz w stos nad przepływie lub jakiś błąd przed nim :).

Jednym ze sposobów na ograniczenie liczby wyników, jest ograniczenie rozmiaru roztworu

phrase(s, X), length(X, 4). 

otrzymuje wszystkie roztwory dokładnie z 4 wartości, która byłaby

X = [a, a, d, d] 
X = [b, b, c, c] 

wzrasta do 6 dałoby :

X = [a, a, a, d, d, d] 
X = [a, b, b, c, c, d] 

lub użyj zakresach:

phrase(s, X), length(X, Y), Y >= 4 , Y < 10, Y != 6.