## 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.)

• 1. The algorithm no longer returns a value. Rather, it prints out parse trees as it finds them.
• 2. At the bottom of the recursion, if the tree is complete, it is displayed.
• 3. the loop through different rules does not terminate if the parse tree is found. Rather, it continues in order to find alternative parse trees.
```
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.

``` 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.

```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 *]

```