쓰기 DCG 특정 숫자의 같은 수의 포함하는 문자열 - 프롤로그

Question

내가 u 및 v은 길이가 같고 ' 0을의 수의 될 필요가 없습니다 곳 u2v의 형태로 문자열을 것이라고 DCG를 작성하는 중이 야

s의 u은 1의 숫자와 동일해야합니다 (v).

지금까지 종이에 작동하는 몇 가지 문법을 작성할 수 있었지만 코드를 작성하고 쿼리를 시도 할 때 일반적으로 어딘가에 루프가 생깁니다. 이것은 내가 얻을 수 있었던 가장 가까운 :

s-->[2]. 
s-->u,[0],n. 
s-->u,s,v. 
n-->s,[1],v. 
u-->[1],u. 
u-->[]. 
v-->[0],v. 
v-->[]. 

나는 것 쿼리 s([0,1,1,2,0,0,1,0],N).에 대한 정답 얻을 수 있습니다 :

N = [] ; 
N = [0] 

을하지만은 후 false으로 종료되지 않습니다 그것은해야한다. 대신 그 답을 반복합니다. Prolog에 대한 지식은 매우 제한되어 있으며 LPN에서 대부분 자체 교습을 해왔으므로 Prolog가 이러한 종류의 것을 평가하는 방법을 이해하지 못하는 것이 더 많은 문제라고 생각합니다. 누군가가 왜 종결되지 않을지 설명 할 수 있다면 그것은 가장 도움이 될 것입니다.

Answer 1

정말 흥미로운 문제입니다!

즉시 내게 떠오르는 것은 문법 구조를 활용하고 싶다는 것입니다. 예를 들어,이 라인을 따라 뭔가를해야 괄호에 맞게 :

expr --> []. 
expr --> ['('], expr, [')']. 

그 방법을, 하나는 괄호 사이에 간다 무엇 이건, 또는 당신은 모든 시간을 좌측 및 오른쪽에 괄호가 있습니다.

이 문제로 이러한 종류의 고장을 해결하는 확실한 방법은 없습니다. 방법이 있을지 모르지만 나는 그것이 무엇인지 보지 못합니다. 그러나 DCGS이 프롤로그의 변수가 작동하는 방식에 대한 서로 다른 해석에 위치, 감사 사이에 주변 정보를 전파 할 수있는 거의 - 초자연적 인 능력을 가지고, 그리고 지금처럼 DCG 규칙에 매개 변수를 작성하여이다 :

rule(Stuff) --> ... 

어쨌든, 다음 스나 푸는 카운트가 인 무언가입니다. 이는 산술이 관련되어있을 수 있음을 의미합니다. 하나! 우리는 Peano 숫자를 사용하여 조금만 속일 수 있습니다. 왜냐하면 우리가 정말로 신경을 쓴 것은 양면에서 서로 같아지기 때문에 결과를 사용자에게 다시 전달할 필요가 없기 때문입니다.

속히

, 여기에 내가 해낸 해결책 :

u2v --> u2v(_). 
u2v(N) --> u(N), [2], v(N). 

u(0) --> []. 
u(s(N)) --> [0], u(N). 
u(N) --> [X], { member(X, [1,2,3,4,5,6,7,8,9]) }, u(N). 

v(0) --> []. 
v(s(N)) --> [1], v(N). 
v(N) --> [X], { member(X, [0,2,3,4,5,6,7,8,9]) }, v(N). 

나는 (심지어 완전히 우수한 방법이있을 수있다)이 코드를 작성하는 더 좋은 방법이 있습니다 확신하지만이 하나에 보인다 내 제한된 테스트에서 작동합니다. 심지어 은이 될 것입니다. 단, 양면의 귀찮은 제한없는 재귀를 제외하고는.

솔루션의 핵심이 라인 :

u2v(N) --> u(N), [2], v(N). 

는 사실, 당신이 N을 보관할 필요가없는,하지만 난 디버깅에 유용하다고. 여기서 중요한 것은 u(N)이 v(N)과 일치한다는 것입니다.그런 다음 u//1과 v//1은 모두 동일한 구조를가집니다. 첫 번째는 아무 것도없는 기본 사례 다음 원하는 숫자와 일치하고 개수를 증가시키는 귀납적 사례 인 Peano 스타일 (0, s (0), s (0)), s (s (s) (0))), ...), 그리고 다른 자릿수와 일치하고 앞의 계수를 앞으로 전달하는 대체 귀납적 인 경우입니다.

succ/2 대신이 작업을 수행하는 것이 가능할 수 있지만 순수 Prolog 비트를 배치해야하는 위치에 대해 걱정합니다. Peano와 함께이 길을가는 것이 나에게 더 단순 해 보였다. (심지어 clpfd 접근법이 있습니다.)

어쨌든, 나는 이것이 도움이되기를 바랍니다!