These exercises are presented in the form of a partial sample exam. They cover the material lectured by Bill Wilson.
THE UNIVERSITY OF NEW SOUTH WALES
Sample Examination (Section B only)
|(1)||TIME ALLOWED - 2 HOURS|
|(2)||TOTAL NUMBER OF QUESTIONS - 9|
|(3)||ANSWER ALL QUESTIONS|
|(4)||QUESTIONS CARRY THE NUMBER OF MARKS INDICATED|
|(5)||TOTAL NUMBER OF MARKS ON PAPER: 100|
CANDIDATE ARE ADVISED TO ALLOCATE THEIR TIME AT 1.8 MINUTES PER MARK.
|(6)||THIS PAPER MAY NOT BE RETAINED BY THE CANDIDATE|
THERE will be 2 SECTIONS in the complete paper
ANSWER EACH SECTION IN A SEPARATE BOOK
ANSWERS MUST BE WRITTEN CLEARLY IN INK. EXCEPT WHERE THEY ARE EXPRESSLY REQUIRED, PENCILS MAY ONLY BE USED FOR DRAWING, SKETCHING, OR GRAPHICAL WORK.
ANSWER IN A SEPARATE BOOK
child_of(mary, steve). child_of(mary, anne). child_of(alice, anne). child_of(alice, steve). child_of(jane, steve). child_of(leslie, steve). female(mary). female(alice). female(jane). sisters(Person1, Person2) :- child_of(Person1, Parent1), child_of(Person1, Parent2), not(Parent1 = Parent2), child_of(Person2, Parent1), child_of(Person2, Parent2), female(Person1), female(Person2), not(Person1 = Person2).
believes(X, likes(mary, pizza)) = believes(frank, likes(Y, pizza))?
Integers and floating point numbers are built into most programming languages, including Prolog. However, suppose that numbers and arithmetic operations were not available. It is still possible to define numbers in Prolog and to write programs to implement simple arithmetic operations. In the following question, you MUST NOT use any of Prologs built-in arithmetic predicates such as is, <, +, *, etc. (except in part (f)). Also, do not use the cut operation (!) in your program.
A positive integer can be defined as zero or the successor of another number. Thus, zero can be represented by 0 and a number, such as two, can be represented by s(s(0)), where two is the successor of the successor of 0. Thus s(X) can be thought of as X+1. We call numbers written like this s-expressions.
In parts (c) to (f), don't worry about what happens if X (and Y and Z) are not s-expressions. You don't have to cope with this, and in particular, you don't have to check for this.
See also the Wikipedia entry on the Peano axioms.
?- s_number(s(s(0))). true.
?- minus1(s(s(0)), Y). Y = s(0) ?- minus1(0, Y). false.
?- subtract(s(s(s(s(0)))), s(s(0)), Z). Z = s(s(0))
Hint - the base case is when Y = 0.
?- value_of(s(s(s(s(0)))), Y). Y = 4
This question is longer than you would get in an actual exam. This way, you get more practice.
Given the following lexicon and grammar information, trace the steps in chart-parsing the two sentences
Lexicon must cover any words to be processed.
|like||PREP, ADJ, VERB, NOUN, ADV, CONJ|
|S → NP VP||TFIF-S1|
|S → VERB NP||TFIF-S2|
|NP → NOUN||TFIF-NP1|
|NP → PRONOUN||TFIF-NP2|
|NP → DET NOUN||TFIF-NP3|
|PP → PREP NP||TFIF-PP1|
|VP → VERB||TFIF-VP1|
|VP → VERB PP||TFIF-VP2|
For each word processed, you should state what new active arcs and what new constituents are added. Report the active arcs in a format exemplified below:
|ARC99: A → B1 * C D 0..1 by rule TFIF-A1||format 1 for reporting active arcs|
|ARC101: A → B1 C1 * D 0..2 from ARC99||format 2 for reporting active arcs|
|A33: A → B1 C2 D3 0..3 by rule TFIF-A1 from ARC101||format 1 for reporting constituents|
|A55: A → B1 4..5 by rule TFIF-A1 & constituent B1||format 2 for reporting constituents|
|E66: E → "word" 4..5 by lexicon entry x||format 3 for reporting constituents|
Rule TFIF-A1 would be a grammar rule that read TFIF-A1: A → B C D, rule TFIF-A1 would be a grammar rule that read TFIF-A1: A → B, and lexicon entry x would read x: word: E ... where the "... " indicates that there could be other lexical categories of which "word" is a member. The label to the left of a new constituent should be of the form <name of the constituent type> followed by a unique identifying number. For example, if the new constituent was an NP, and it was the third one found by the algorithm, you could call it NP3.
It is not necessary to draw a diagram showing constituents and/or arcs - you can if you want to.
Solutions (when available)
CRICOS Provider Code No. 00098G