Problem 1. The predicate ``length(L,N)'' is supposed to bind M to be the length of L. Thus, ``length([a,b,c,d],N)'' should succeed with N bound to 4. Which of the following definitions is correct: (Only one is.) A. length([],0). length([X|L],N) :- length(L,N) + 1. B. length([],0). length([X|L],N) :- length(L,N), N is N+1. C. length([],0). length([X|L], N+1) :- length(L,N). D. length([],0). length([X|L], N) :- N1 is N-1, length(L,N1). E. length([],0). length([X|L],N) :- length(L,N1), N is N1+1. Answer: E Problem 2. The Prolog query ?- [X,Y | L] = [a,b,c] A. Succeeds once with X=a, Y=b, L=c. B. Succeeds once with X=a, Y=b, L=[c]. C. Succeeds once with X=[a], Y=[b], L=[c]. D. Succeeds many times: First with X=[], Y=[], L=[a,b,c]; next, on backtracking with X=[], Y=[a], L=[b,c]; and so on through the various divisions of the list [a,b,c]. E. Fails. Answer: B Problem 3. Compositional semantics is A. The principle that the meaning of a sentence is derived by combining the meanings of the words in a mode indicated by the syntactic structure. B. A technique for applying world knowledge to semantic interpretation. C. The problem of giving an interpretation to a text of many sentences. D. A method of disambiguation. E. The decomposition of a word into a root and its inflections, prefixes and suffixes. Answer: A Problem 4. In a Markov model A. Node N is labelled with the probability of being at N. B. Node N is labelled with the probability that you will start at N. C. The arc from node N to M is labelled with the probability of going to M, given that you are now at N. D. The arc from node N to M is labelled with the probability that you just came from M, given that you are now at M. E. The arc from node N to M is labelled with the probability that your last transition was from N to M. Answer: C. Part II. (20 points each) Problem 5. Suppose that you have the following small family tree in Prolog parent(philip, charles). parent(philip,anne). parent(charles, william). Further, you have the following recursive definition of ``ancestor'': ancestor(X,X). ancestor(X,Z) :- parent(X,Y), ancestor(Y,Z). Now a user comes and issues the query ?- ancestor(A,B). Each time that Prolog returns an answer, the user inputs `;' to ask it to look for another answer. What answers does Prolog return, and in what order? Answer: A = X, B = X ; A = philip, B = charles ; A = philip, B = william ; A = philip, B = anne ; A = charles, B = william ; no. Problem 6. List the major modules of a natural language interpretation system and explain their function. Answer: The earliest level of analysis converts the raw data into a series of words. If the original medium of the text is speech, then this is speech understanding; if it is printed then this is print or handwriting recognition; if it is electronic, then nothing need be done. Morphology analyzes the structure of words, extracting the root or roots, prefixes, suffixes, and inflections. The syntactic parser takes as input a sentence as a sequence of words or morphemes. It outputs a syntax tree that expresses the grammatical structure of the sentence. The semantic analyzer takes as input a syntax tree for a sentence. It outputs a representation of the meaning of the sentence. Discourse or text analysis takes as input the meaning representation of each sentence in the text. It connects these together to produce a meaning representation for the entire text. Problem 7. Consider the grammar defined by the following BNF: S -> NP VP NP -> | PP* | NP "and" NP VP -> { NP } { NP } PP* PP -> NP Vocabulary: "John" : "Mary" : "rose" : , "saw" : , "morning" : "gave" : "the" : "to" : "in" : A. For each of the following sentences, draw all the parse trees, if any, in this grammar for the sentence. 1. John gave Mary the rose. 2. Mary gave the rose to John. 3. John and Mary saw the rose. 4. John rose in the morning. 5. John rose and saw the morning. 1. S_____ | | NP VP________ | | | | | | NP NP___ | | | | | name verb name det noun | | | | | John gave Mary the rose. 2. S_____ | | NP VP_____________ | | | | | | NP___ PP___ | | | | | | | | | | | NP | | | | | | name verb det noun prep name | | | | | | Mary gave the rose to John S_____ | | NP VP____ | | | | | NP________ | | | | | | | | | PP____ | | | | | | | | | | | NP | | | | | | name verb det noun prep name | | | | | | Mary gave the rose to John 3. S______________ | | NP________ VP____ | | | | | NP | NP | NP___ | | | | | | name name verb det noun | | | | | | John and Mary saw the rose 4. S_____ | | NP VP____ | | | | | PP____ | | | | | | | NP___ | | | | | name verb prep det noun | | | | | John rose in the morning 5. No parse for this sentence B. Give an example of a meaningless sentence in this grammar with this vocabulary. Answer: "John gave the morning" "The morning gave Mary" (many others) C. Are there a finite or an infinite number of sentences in the language defined by this grammar and vocabulary? Answer: Infinitely many. (E.g. "John saw Mary in the morning in the morning in the morning ..." "John and Mary and John and Mary ... saw the rose.") Problem 8. Give an example of a sentence or pair of sentences in which selectional restrictions can be used to disambiguate potential anaphoric ambiguity. Explain the ambiguity and the selectional restriction used. Example: "John ate his breakfast while he looked at the rose out the window." It was beginning to blossom." Here "It" refers to "rose" rather than "breakfast" or "window". "Blossom", in the literal meaning, is restricted to take a plant as subject; thus "breakfast" and "window" are excluded.