Assignment 4, Ling 645/CMSC 723, Fall 1997

Assignment 4, Ling 645/CMSC 723, Fall 1997

```
For this assignment, you are required to do TWO OUT OF FOUR of the
problems below (i.e. two out of {4.1, 4.2, 4.3, 4.4}, doing all parts
within each problem).  You are welcome (indeed, encouraged!) to do
three or all four if you'd like, in which case I will take the two
problems with the highest scores for grading purposes.  In any case,
solutions when I give them out.

Problem 4.1 [50 pts]

Given the following grammar:

S   -> NP VP
NP  -> DET N
NP  -> NP PP
VP  -> V NP
VP  -> VP PP
PP  -> P NP
N   -> chef | customer | sushi | restaurant
P   -> in | from
V   -> liked | likes | hated
DET -> the

Show

(a)  The table that results from running the CKY algorithm
on the sentence "the chef liked the sushi in the restaurant"

(b)  The corresponding chart (well formed substring table)

Recall that a chart, or well formed substring table, has the
sentence at the bottom of it, with labeled arcs spanning sequences
of words.  For example, if the grammar was

S  -> NP VP
NP -> N
VP -> V NP
N -> edgar | sushi
V -> liked | hated

then the chart for "edgar liked sushi" would look like this:

________S_______________
|        _____VP________ |
|       |               ||
| __NP_ |         __NP_ ||
||     ||        |     |||
| __N__ | __V__   __N__ ||
||     |||     | |     |||
edgar   liked   sushi

If you'd prefer, you can use notation like Allen, Figures 3.15 (p. 60)

Problem 4.2 [50pts]

(a) Given the same grammar as in 4.1(a), show the sequence of stack
configurations when recognizing the same sentence using the
left-corner algorithm we used in class.  There are two
different successful paths you can take; choose the one where
"the sushi in the restaurant" is treated as the NP object of
the verb.

To start you off (and show what to turn in):

----------------------------------------------------------------------
Operation      Stack                          Next word in the input
----------------------------------------------------------------------
START          ()                             the
shift          ([Det,()])                     chef
...etc.

(b)  Draw the parse tree for this analysis (in the style of
Allen, Figure 3.1, p. 42).

(c)  How is the depth of the stack related to the tree structure?
In particular, looking at a parse tree like the one you just drew,
how can you determine what the maximum depth of the stack is
going to be (for the above left-corner parser)?

Problem 4.3 [50 pts]

(a) Given the same grammar as in 4.1(a), show the operation
of the Earley parser we discussed in class.  For each
state in a state set, name the operation that was used to
add that state (scan, predict, or complete), just as in the
example we went over in class.

(b) Suppose that in order to accept sentences like

the chef that the customer liked hated the sushi
the customer liked the sushi that the chef hated

NP   -> NP REL
REL  -> that S
NP   -> epsilon

to the grammar of 4.1(a), where epsilon represents the empty
string.

(i) Give two example sentences showing how the extended
grammar overgenerates (i.e. sentences not grammatical
in English that the grammar nonetheless generates).

(ii) Would having nonterminals that expand to epsilon
affect the Earley parsing algorithm; that is, would
you need to change the algorithm to accommodate them?
Explain.

Problem 4.4 [50 pts]

(a) Consider the following data:

(1)a. I dislike and Warren enjoys going to the Italian opera.
b. The chef served Edgar sushi and Edna jambalaya.

Why does the conjunction test for constituency (Allen, pp. 44-45)
suggest that these examples might be a problem for context-free
approaches to grammar, at least those following the outline
of English syntax in Allen, Section 2.3?

(b) Consider the following sentence:

The mouse that the cat that the dog chased bit died

Identify the nested dependencies in this sentence, showing
which words are related and identifying the syntactic
relationship between them.  Do the same for

John saw the dog that chased the cat that bit the mouse that died

Assuming the human sentence processor was something like the
bottom-up or left-corner stack based parsers we've discussed in
class, why might the second sentence be easier to process than
the first one?

```