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.