Câu hỏi - ngôn ngữ chính thức trong prolog

Question

Tôi đang cố gắng xây dựng một DCG công nhận tất cả các danh sách khớp với biểu mẫu này: a^n b^2m c^2m d^n.
Tôi đã viết lên các quy tắc sau:
s --> [].
s --> ad.
ad --> a, ad, d.
ad --> bc.
bc --> b, b, bc, c, c.
bc --> [].
a --> [a].
b --> [b].
c --> [c].
d --> [d].

Khi tôi cố gắng đánh giá chuỗi có thông số kỹ thuật đó, như danh sách [a,b,b,c,c,d], nó hoạt động. Nhưng khi tôi cố gắng đánh giá truy vấn phrase(s, X) để tôi có thể thấy tất cả các chuỗi có thể được trả về bởi ngữ pháp này, nó lặp lại vô cùng.

Có điều gì sai với cách tôi tạo DCG không?

Answer 1

Bạn có thể liệt kê các chuỗi công bằng với chiều sâu lặp đi lặp lại:

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

Answer 2

Tôi không thấy phần mở đầu của câu hỏi này. Câu trả lời rất phụ thuộc vào cách bạn thực hiện ngữ pháp này.

Dự đoán tốt nhất của tôi là đảo ngược thứ tự các quy tắc, để áp dụng quy tắc chấm dứt trước.

Answer 3

tôi đã viết này như là một cách để giúp các giải pháp hạn chế mặc dù có những giải pháp vô hạn. Nhưng tôi nhận ra sẽ có một cách để sắp xếp lại các quy tắc để có được kết quả ngắn hơn trước.

Vì ad --> a, ad, d. được đánh giá trước ad --> bc., hãy cố gắng đáp ứng ad --> a, ad, a. trước ad --> bc.. Tôi sẽ đặt ad --> bc. trước ad --> a, ad, a.. Điều tương tự cũng áp dụng cho các quy tắc bc --> b, b, bc, c, c. và bc --> [].

Do arian đã chỉ ra quy tắc chấm dứt được áp dụng trước tiên, nên đảm bảo các giải pháp ngắn hơn được tìm thấy trước tiên.

Tôi cũng muốn chỉ ra rằng có hai giải pháp cho [] s và s -> quảng cáo -> bc -> [] Tôi sẽ loại bỏ s --> []. vì nó không cần thiết.

Tất cả trong tất cả tôi sẽ cố gắng giải pháp này:

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

POST ORIGINAL:

Tôi phải bất lực nhìn lên thế nào để làm đếm (nó được một lúc kể từ khi tôi đã làm prolog) Nhưng có một số vô hạn và kể từ khi prolog cố gắng tìm tất cả các giải pháp nó không bao giờ ngừng tìm kiếm, mặc dù tôi chắc chắn bạn sẽ nhấn một chồng trên dòng chảy hoặc một số lỗi trước đó :).

Một cách để hạn chế số lượng kết quả là để giới hạn kích thước của giải pháp

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

Gets tất cả các giải pháp với chính xác 4 giá trị, đó sẽ là

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

tăng đến 6 sẽ mang lại :

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

Hoặc phạm vi sử dụng:

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