Assignment 3

Prolog -- the beginning

Due date:
Feburary 25. 11:59pm.

Read chapters 1-4 in Prolog: A Tutorial Introduction. While not required I strongly recommend that you work through many of the examples.

SWI Prolog -- the one described in the Tutorial -- is available on the cs department machines using the command "pl". Should you want it on a personal machine there are versions for Unix, PC and Mac from SWI.

Thoughts. If you use swi under windows:

• I found it necessary to skip a line between each prolog statement in the files I was editing.
• I had success using the load menu to refresh the program in the interpreter. The method described in the tutorial worked, but with difficulty
• there is a very useful piece of documentation in pl/doc/windows.html.

• To quit prolog enter ctrl-d.
• Things follow the tutorial quite closely

Do

1. Problem 1 (page 5).
2. Problem 3 (pages 10 and 11). Do part 2. In the family tree problem, the only facts in the system should be male, female, sibling, and parent. All others (brother, sister, father, mother, son, daughter, grandmother, grandfather, uncle, aunt and cousin) should be rules. (Note that this means your implementation should not exactly follow that in the tutorial.) For example below is a set of rules and facts. You could use these to prove that geoff is the brother of jen. (I really do have a sister named Jen.)

   male(geoff).
   sibling(geoff, jen).
   brother(X, Y) :- male(X), sibling(X, Y).
   

   Do not be limited by this example or the suggestions in the tutorial. You need not be exhaustive (or even truthful) about your family. Just give enough to show that everything works.
3. (20 points) Recognise all strings of the form a*b*. E.g., "ab", "aaaaaaabbb". Note that the * indicates 0 or more occurrences of a letter. Do this as a list. For example, is your rule was named acceptaabb, then a test returning yes would look like acceptaabb([a,a,a,b,b,b,b,b,b,b]).
   Examples:
   Yes: [], [a], [a,a,a,a], [b,b,b,b], [a,a,a,b,b,b,b,b,b,b]
   No: [c], [a,b,c], [c,a,b], [a,b,a]
4. (20 points) Recognize all strings of the form (abcd)*. E.g., "abcd", "abcdabcdabcd". As above * indicates 0 or more occurrences, in this case of "abcd". As with the previous question, do this as a list. For example, is your rule was named acceptabdc, then a test returning yes would look like acceptaabb([a,b,c,d,a,b,c,d]).
   Examples:
   Yes: [], [a,b,c,d], [a,b,c,d,a,b,c,d]
   No: [c], [a,b,c], [c,a,b], [a,b,a], [a,b,c,d,a]

Hand in: