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

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

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.