1

Define a relation xyz(X) that is true if X is a xyz sequence. A xyz sequence is a sequence that consists of either the number 0, or the number 1 followed by two other xyz sequences.

Some xyz sequences:

xyz([0]).
xyz([1,0,1,0,0]).

And, the following are not considered xyz sequences:

xyz([1,1,0,0]).
xyz([0,1,0]).
xyz([1,1,0]).
xyz([1,0,1,1,1,1,1,0,1]).

Can someone help me with how to approach this problem?

mat
  • 40,498
  • 3
  • 51
  • 78
am3decoy
  • 73
  • 5
  • This question is related: http://stackoverflow.com/questions/24313936/solution-to-smullyans-numerical-machines – false Mar 06 '15 at 20:46

2 Answers2

3

The easiest is to write a DCG. See this tutorial for a thorough introduction. You can literally write down the problem statement verbatim to get a solution:

xyz --> [0].
xyz --> [1], xyz, xyz.

You will need phrase:

?- phrase(xyz, [1,0,1,0,0]).

This solution leaves behind a choice point.

  • I didn't know about DCG before, it looks like some powerful stuff. I appreciate you sharing that information. How would I go about implementing those DCG rules within the `xyz(A)` predicate so that to get 'true', I don't have to type in `phrase(xyz, [0])' and instead I can query with `xyz([0]`? – am3decoy Mar 06 '15 at 07:38
  • 1
    Never mind, it was pretty simple. `xyz(A):- phrase(xyz,A).` after those DCG rules. Looks good, right? – am3decoy Mar 06 '15 at 07:41
  • 1
    @am3decoy Yes, this is pretty much it, if you don't want to call `phrase` yourself in your predicate. It is up to you if you want to be explicit about the call to `phrase` of if you want to hide it: I prefer to use it directly, but this is a matter of taste. –  Mar 06 '15 at 07:50
  • @am3decoy And keep in mind that a DCG is not exactly the same as pattern matching: you write a grammar, not just a pattern (as in regex). –  Mar 06 '15 at 07:53
  • Yeah, I'm going to be looking into this further. Hey if you don't mind, do you think you can look at one of my other questions? I have it figured out thanks to one of the users here, I just need to know how to reverse the list. I tried different ways to reverse the list, but I had no success. The code is `xyz(X, Y):- f(X, Z,_) -> findall([A|B], (member(A, Z), xyz(A, B)), L), flatten(L, F), sort(F, Y); Y = [].` I simply need the list that gets outputted by this in reverse. http://stackoverflow.com/questions/28845949/recursion-in-prolog/28850778?noredirect=1#comment45994124_28850778 – am3decoy Mar 06 '15 at 07:57
  • @am3decoy You have already gotten an answer, and you have accepted it. In such cases, instead of editing your question, adding to it, it is best to ask a _new_ question. So go ahead and do it. You can pretty much copy the second part of the original question to a new question. You can also link your own old question in the new question, if you feel it is useful. –  Mar 06 '15 at 08:09
  • That makes sense since it's going to be available to others who are seeking assistance with the same issue. I've created a new post. Please take a look at your earliest. Thanks! http://stackoverflow.com/questions/28894594/prolog-need-help-reversing-a-list – am3decoy Mar 06 '15 at 08:14
0

such simple grammar is ideal to understand the mechanism (albeit simplified) that powers DCGs:

seq(S) :- seq(S, []).

seq([0|R], R).
seq([1|T], R) :- seq(T, Q), seq(Q, R).
false
  • 10,264
  • 13
  • 101
  • 209
CapelliC
  • 59,646
  • 5
  • 47
  • 90