Sample Mid-Term Exam

I will hand out the answers and discuss them on Tuesday, Oct. 16.

Problem 1

Consider the following CFG grammar:
S -> NP VP
NP -> NG | NG "and" NG
NG -> pronoun | noun
VP -> verb | verb NP | VP "and" VP

I : pronoun.
cook : noun, verb
eggs : noun
fish : noun, verb.
Which of the following parse tree are correct:
i.  S ---> NP ---> NG ---> pronoun ---> I
       |-> VP ---> verb ---> cook
               |-> NP ---> NG ---> noun ---> eggs
                       |-> "and"
                       |-> NG ---> noun ---> fish

ii. S ---> NP ---> NG ---> pronoun ---> I
       |-> VP ---> verb ---> cook
               |-> NP ---> NG ---> noun ---> eggs
                       |-> "and"
                       |-> VP ---> verb ---> fish

iii.S ---> NP ---> NG ---> pronoun ---> I
       |-> VP ---> VP ---> verb ---> cook
               |       |       
               |       |-> NP ---> NG ---> noun ---> eggs
               |-> "and"
               |-> VP ---> verb ---> fish

iv. S ---> NP ---> NG ---> pronoun ---> I
       |-> VP ---> verb ---> cook
               |-> NP ---> NG ---> noun ---> eggs
               |-> "and"
               |-> VP ---> verb ---> fish
A. All four.
B. Only (i)
C. (i), (iii), and (iv).
D. (i) and (iii).
E. (i) and (iv).

Problem 2

Suppose that a chart parser is parsing the sentence in problem 1 using the grammar in problem 1. Which of the following edges corresponds to parse tree number (i) (there may be more than one):
A. [2,2,NP -> * NG]
B. [2,2, NP -> * NG "and" NG]
C. [2,3,NP -> NG *]
D. [2,4,NP -> NG "and" *]
E. [2,4,NP -> NG "and" * NG]
F. [4,5,NP -> NG *]

Problem 3

Convert the following sentence to CNF:
(P <=> Q) => R.

Problem 4

Trace the workings of the Davis-Putnam procedure on the set of clauses.
1. ~P V Q V R
2. P V ~Q
3. P V ~R
4. ~P V ~Q V S
5. ~Q V R V ~S
6. ~R V ~S
7. ~A V P.
8. ~A V R.

Problem 5

Let G be an undirected graph. An independent set in G is a set of vertices Z such that no two vertices I,J in Z are connected by an edge. For instance, in the graph shown below, the set { E,F,H } is an independent set because the graph does not contain any of the edges EF, EH, or FH.

The INDEPENDENT SET problem is, given a graph G and an integer K, find an independent set in G of size K.

An instance of the INDEPENDENT SET problem can be translated into propositional satisfiability as follows: For each vertex V and for each integer I=1 .. K, define the atom V_I to be the assertion that V is the Ith vertex, alphabetically, in the set Z. Define the atom V_in to be the assertion that V is in the set Z. One then needs the following four types of constraints:

  1. V is in Z if and only if V is the Ith vertex in Z for some value of I.
  2. For I > 1, if V is the Ith vertex in Z then one of the vertices alphabetically before V is the (I-1)st vertex in Z. (If V is the first vertex alphabetically in G, then this amounts to the statement that V is not the second or third or fourth ... or Kth vertex in Z.)
  3. If U and V are connected in G then U and V are not both in Z.
  4. Some vertex is the Kth vertex in Z.
Give one instance of each of these four types of constraints that would be generated for the above graph with K=3.

Problem 6:

Consider a domain where the individuals are people and languages. Let Z be the first-order language with the following primitives:
s(X,L) --- Person X speaks language L.
c(X,Y) --- Persons X and Y can communicate.
i(W,X,Y) --- Person W can serve as an interpreter between persons X and Y.
j,p,m,e,f --- Constants: Joe, Pierre, Marie, English, and French respectively.

A. Express the following statements in Z:

B. Show how sentences (i), (ii), (iii), (v), and (vi) can be expressed in Datalog. (Hint: Sentences (i) and (v) each turn into two facts in Datalog.)

C. Explain why sentence (iv) cannot be expressed in Datalog.

D. Show how (vi) can be proven from (i), (ii), (iii) and (v) using forward chaining.

D. Show how (vi) can be proven from (i), (ii), (iii) and (v) using backward chaining.

Problem 8

Consider the following pair of sentences:
A. Joe wore a wool suit. ("suit" = pants and jacket)
B. The suit is in the court. ("suit" = lawsuit).
Explain how the disambiguation techniques of selectional restriction and frequency in context can be applied in these two sentences.