Problem Set 6

Assigned: November 7
Due: November 14.

General Description

Consider the following grammar and lexicon:

Grammar

S -> NP VP
NP -> Noun
NP -> NP PP
NP -> NP "and" NP
VP -> Verb
VP -> Verb NP
VP -> VP PP
VP -> VP "and" VP
PP -> Prep NP

Lexicon

bikes -- Noun, Verb
fields -- Noun, Verb
fishes -- Noun, Verb
in -- Prep
John -- Noun
streams -- Noun, Verb
through -- Prep

Problem 1:

Show all possible parse trees for "John fishes in streams and bikes through fields."

Problem 2:

Show all the edges constructed by a top-down chart parser for the sentence, "John fishes in streams". Identify the edges that are part of the final complete parse tree.