Introduction to Artificial Intelligence: Problem Set 3

Assigned: Jan. 31
Due: Feb. 7

Problem 1

The routines in the class notes on parsing return a single parse tree. Suppose, instead, you want to print out all possible parse tree. Show how Algorithm 2, the "Deterministic algorithm for parsing CFG's top-down using DFS," can be modified to do this. (You may assume that there is a subroutine available "display(T)" that prints out a parse tree T.)

Answer: The answer is displayed below. Note the following changes:


parse1(in Q : sentence; G : set of CFG rules; T_IN : parse tree;)

begin if all the leaves in T_IN are terminals
         then if words in Q are all attached to T_IN
                 then display(T_IN) 
              endif
  else begin    
      L := leftmost non-terminal in T_IN;
      if L is a part-of-speech
        then W := first word in Q not attached to T_IN;
             if L is a possible part of speech for W
               then begin make W a child of L;
                          parse1(Q,G,T_IN)
                     end
             endif
        else for each rule in G of form "L -> RHS"
                    create chidren for L with non-terminals RHS;
                    parse1(Q,G,T_IN0
                endfor
         endif

end

Problem 2

Consider the following simple grammar:

Phrase markers

S -> NP VP
NP -> Pronoun
NP -> NG
NP -> NG PP
NG -> Noun
NG -> Determiner Noun
VP -> VG
VP -> VG NP
VP -> VG PP
VP -> VG NP PP
VG -> Verb
VG -> Modal Verb
PP -> Preposition NP

Lexicon

"can" : Modal, Noun, Verb
"fish": Noun, Verb
"I"   : Pronoun
"lake": Noun
"on"  : Preposition
"the" : Determiner

A. Show all the possible parse trees for the sentence "I can fish on the lake" under this grammar.

Answer

 Tree 1  

S ---> NP ---> Pronoun ---> I
   |
   |-> VP ---> VG ---> Modal ---> can
           |       |
           |       |-> Verb ---> fish
           |
           |-> PP ---> Preposition ---> on
                   |
                   |-> NP ---> Determiner ---> the
                           |
                           |-> Noun ---> lake.

 Tree 2  

S ---> NP ---> Pronoun ---> I
   |
   |-> VP ---> VG ---> Verb ---> can
           |       
           |-> NP ---> NG ---> Noun ---> fish
           |
           |-> PP ---> Preposition ---> on
                   |
                   |-> NP ---> Determiner ---> the
                           |
                           |-> Noun ---> lake.

 Tree 3  

S ---> NP ---> Pronoun ---> I
   |
   |-> VP ---> VG ---> Verb ---> can
           |       
           |-> NP ---> NG ---> Noun ---> fish
                   |
                   |-> PP ---> Preposition ---> on
                           |
                           |-> NP ---> Determiner ---> the
                                   |
                                   |-> Noun ---> lake.

B. Show how the chart parser (Russell and Norvig, pp. 696-702) parses this sentence using this grammar. Specifically, you should construct a table analogous to Figure 23.4 (p. 700) for this sentence and this grammar, showing all the edges in the chart and how they are formed.

Answer

Edge     Procedure       Derivation
 a       INITIALIZER     [0,0,S' -> * S]
 b       PREDICTOR(a)    [0,0,S  -> * NP VP]
 c       PREDICTOR(b)    [0,0,NP -> * Pronoun]
 d       PREDICTOR(b)    [0,0,NP -> * NG ]
 e       PREDICTOR(b)    [0,0,NP -> * NG PP]
 f       SCANNER(c)      [0,1,NP -> Pronoun *]
 g       COMPLETER(b,f)  [0,1,S  -> NP * VP ]
 h       PREDICTOR(d)    [0,0,NG -> * Noun]
 i       PREDICTOR(e)    [0,0,NG -> * Determiner Noun]
 j       PREDICTOR(g)    [1,1,VP -> * VG]
 k       PREDICTOR(g)    [1,1,VP -> * VG NP]
 l       PREDICTOR(g)    [1,1,VP -> * VG PP]
 m       PREDICTOR(g)    [1,1,VP -> * VG NP PP]
 n       PREDICTOR(j)    [1,1,VG -> * Verb]
 o       PREDICTOR(j)    [1,1,VG -> * Modal Verb]
 p       SCANNER(n)      [1,2,VG -> Verb *]
 q       COMPLETER(j,p)  [1,2,VP -> VG *]
 r       COMPLETER(g,q)  [0,2,S -> NP VP *] 
 s       COMPLETER(a,r)  [0,2,S' -> S*]
 t       COMPLETER(k,p)  [1,2,VP -> VG * NP]
 u       COMPLETER(l,p)  [1,2,VP -> VG * PP]
 v       COMPLETER(m,p)  [1,2,VP -> VG * NP PP]
 w       SCANNER(o)      [1,2,VG -> Modal * Verb]
 x       SCANNER(w)      [1,3,VG -> Modal Verb *]
 y       COMPLETER(j,x)  [1,3,VP -> VG *]
 z       COMPLETER(g,y)  [0,3,S -> NP VP *]
 aa      COMPLETER(a,z)  [0,3,S' -> S *]
 ab      PREDICTOR(t)    [2,2,NP -> * Pronoun]
 ac      PREDICTOR(t)    [2,2,NP -> * NG]
 ad      PREDICTOR(t)    [2,2,NP -> * NG PP]
 ae      PREDICTOR(u)    [2,2,PP -> * Preposition NP]
 af      PREDICTOR(ac)   [2,2,NG -> * Noun]
 ag      PREDICTOR(ac)   [2,2,NG -> * Determiner Noun]
 ah      SCANNER(af)     [2,3,NG -> Noun *] 
 ai      COMPLETER(ac,ah)[2,3,NP -> NG *]
 aj      COMPLETER(ad,ah)[2,3,NP -> NG * PP]
 al      COMPLETER(t,aj) [1,3,VP -> VG NP *]
 am      COMPLETER(v,aj) [1,3,VP -> VG NP * PP]
 an      COMPLETER(g,al) [1,3,S -> NP VP *]
 ao      COMPLETER(a,an) [1,3,S' -> S *]
 ap      PREDICTOR(aj)   [3,3,PP -> * Preposition NP]
 aq      SCANNER(ap)     [3,4,PP -> Preposition * NP]
 ar      PREDICTOR(aq)   [4,4,NP -> * Pronoun]
 as      PREDICTOR(aq)   [4,4,NP -> * NG]
 at      PREDICTOR(aq)   [4,4,NP -> * NG PP]
 au      PREDICTOR(at)   [4,4,NG -> * Noun]
 av      PREDICTOR(at)   [4,4,NG -> * Determiner Noun]
 aw      SCANNER(av)     [4,5,NG -> Determiner * Noun]
 ax      SCANNER(aw)     [4,6,NG -> Determiner Noun *]
 ay      COMPLETER(as,ax)[4,6,NP -> NG *]
 az      COMPLETER(at,ax)[4,6,NP -> NG * PP]
 ba      COMPLETER(aq,ay)[3,6,PP -> Preposition NP *]
 bb      COMPLETER(aj,ba)[2,6,NP -> NG PP *]
 bc      COMPLETER(am,ba)[1,6,VP -> VG NP PP *]
 bd      COMPLETER(t,bb) [1,6,VP -> VG NP *]
 be      COMPLETER(g,bc) [0,6,S -> NP VP *]
 bf      COMPLETER(a,be) [0,6,S' -> S *]