Assignment 4 solutions, Ling 645/CMSC 723, Fall 1997

# Assignment 4 solutions, Ling 645/CMSC 723, Fall 1997

```

4.1.a  CKY table for "the chef liked the sushi in the restaurant"

the          chef   liked     the   sushi    in       the   restaurant
1            2       3        4      5       6        7       8
1 { DET }      { N }   { V }   { DET } { N }   { P }   { DET }  { N }
2 { NP }       { }     { }     { NP }  { }     { }     { NP }
3 { }          { }     { VP }  { }     { }     { PP }
4 { }          { }     { }     { }     { }
5 { S }        { }     { }     { NP }
6 { }          { }     { VP }
7 { }          { }
8 { S }

4.1.b  Chart (on-paper solution in Ling 645 folder, 1401 Marie Mount Hall)

4.2.a

START       ()
shift       [DET,()]                                             the
LC-predict  [NP,(N)]                                             chef
shift       [N,()][NP,(N)]                                       liked
combine     [NP,()]                                              liked
LC-predict  [S,(VP)]                                             liked
shift       [V,()][S,(VP)]                                       the
LC-predict  [VP,(NP)][S,(VP)]                                    the
shift       [DET,()][VP,(NP)][S,(VP)]                            sushi
LC-predict  [NP,(N)][VP,(NP)][S,(VP)]                            sushi
shift       [N,()][NP,(N)][VP,(NP)][S,(VP)]                      in
combine     [NP,()][VP,(NP)][S,(VP)]                             in
*LC-predict  [NP,(PP)][VP,(NP)][S,(VP)]                           in
shift       [P,()][NP,(PP)][VP,(NP)][S,(VP)]                     the
LC-predict  [PP,(NP)][NP,(PP)][VP,(NP)][S,(VP)]                  the
shift       [DET,()][PP,(NP)][NP,(PP)][VP,(NP)][S,(VP)]          restaurant
LC-predict  [NP,(N)][PP,(NP)][NP,(PP)][VP,(NP)][S,(VP)]          restaurant
shift       [N,()][NP,(N)][PP,(NP)][NP,(PP)][VP,(NP)][S,(VP)]    (empty)
combine     [NP,()][PP,(NP)][NP,(PP)][VP,(NP)][S,(VP)]           (empty)
combine     [PP,(NP)][NP,(PP)][VP,(NP)][S,(VP)]                  (empty)
combine     [NP,()][VP,(NP)][S,(VP)]                             (empty)
combine     [VP,()][S,(VP)]                                      (empty)
combine     [S,()]                                               (empty)
ACCEPT

(*The starred configuration is the one where you would branch off
if you wanted the parse where PP is adjoined to the VP.  Instead of
LC-prediction, you'd do a combine of the incomplete VP with the
completed NP, and then do left-corner prediction to get [VP,(PP)].)

4.2.b

_________S___
|       ______VP___
|      |       ____NP__
|      |      |        _PP_
|      |      |       |    |
__NP__    |    __NP__    |  __NP__
|    |    |    |    |    |  |     |
DET  N    V    DET  N    P  DET   N
|   |    |    |    |    |   |    |
the chef liked the sushi in the restaurant

4.2.c

The depth of the stack is related to the number of incomplete
constituents being worked on, and because the parser is essentially
bottom-up, constituents are incomplete until their RIGHTMOST
sub-constituent is completed.  For example, the S is incomplete until
the VP is completed, the VP is incomplete until the NP is completed,
etc.  So the maximum depth of the stack is going to correspond to
the maximum length of such a chain of incomplete rightmost
constituents -- in this case that's S-VP-NP-PP-NP-N, which is 6.

Incidentally, a  structure is called RIGHT BRANCHING, when
the remaining material in the string is covered by the rightmost
child.  So the parse tree above is essentially right branching.

4.3.a

S0 (Initialization):

(Start -> * S, NIL, 0) - initial
(S -> * NP VP, 0, 0) - pred
(NP -> * DET N, 0, 0) - pred
(NP -> * NP PP, 0, 0) - pred

S1: Word - The

(NP -> DET * N, 0, 1) - scan

S2: Word - chef

(NP -> DET N *, 0, 2) - scan
(S -> NP * VP, 0, 2) - complete
(NP -> NP * PP, 0, 2) - complete
(VP -> * V NP, 2, 2) - predict
(VP -> * VP PP, 2, 2) - predict
(PP -> * P NP, 2, 2) - predict

S3: Word - liked

(VP -> V * NP, 2, 3) - scan
(NP -> * DET N, 3, 3) - pred
(NP -> * NP PP, 3, 3) - pred

S4: Word - the

(NP -> DET * N, 3, 4) - scan

S5: Word - sushi

(NP -> DET N *, 3, 5) - scan
(VP -> V NP *, 2, 5) - complete
(NP -> NP * PP, 3, 5) - complete
(S -> NP VP *, 0, 5) - complete
(VP -> VP * PP, 2, 5) - complete
(PP -> * P NP 5, 5) - predict
(Start -> S *, nil, 5) - complete

S6: Word - in

(PP -> P * NP, 5, 6) - scan
(NP -> * DET N, 6, 6) - predict
(NP -> * NP PP, 6, 6) - predict

S7: Word - the

(NP -> DET * N, 6, 7) - scan

S8: Word - restaurant

(NP -> DET N *, 6, 8) - scan
(PP -> P NP *, 5, 8) - complete
(NP -> NP * PP, 6, 8) - complete
(VP -> VP PP *, 2, 8) - complete
(NP -> NP PP *, 3, 8) - complete
(PP -> * P NP, 8, 8) - predict
(S -> NP VP *, 0, 8) - complete
(VP -> VP * PP, 2, 8) - complete
(VP -> V NP *, 2, 8) - complete
(NP -> NP * PP, 3, 8) -    complete
(Start -> S *, NIL, 8) - complete

4.3.b

(i)   There are lots of sentences that the grammar would accept
incorrectly, involving either an empty NP where none
is allowed (e.g. "liked the sushi") or a non-empty NP
in an improper context (e.g. "the chef that the customer liked
the restaurant hated the sushi").

(ii)  The algorithm as written can handle empty strings.
Suppose N -> epsilon is a rule of the grammar.  When you
do "predict" on

[A -> alpha . N beta, k, i]

you will introduce

[N -> . epsilon, i, i]

But since epsilon is the empty string, this is equivalent to

[N -> epsilon . , i, i]

So the "complete" operation can combine

[A -> alpha . N beta, k, i]
[N -> epsilon . , i, i]

to get

[A -> alpha N . beta, k, i]

High partial credit will be assigned to answers that say
the algorithm does need to be changed, if a reasonable change
is given. For example, it would be reasonable to suggest
adding an extra	operation that takes

[A -> alpha . N beta, k, i]     in S_i
to

[A -> alpha N . beta, k, i]     in S_i

when N -> epsilon.

4.4.a

The conjunction test suggests that "I dislike" and "Warren enjoys" are
constituents, but the standard view of English grammar does not permit
a constituent that contains the subject and verb but not the verb's
object.  Similarly for ditransitive constructions: the standard view
of grammar does not group the direct and indirect object into a single
constituent not containing the verb.

Other alternatives involve, say, movement and/or deletion, e.g.
deriving

The chef served Edgar sushi and Edna jambalaya

from

The chef [VP served Edgar sushi] and [VP served Edna jambalaya]

by deleting the verb from the second VP.  But grammars of the kind
we've considered so far do not permit a deletion operation; it's
outside the capabilities of the formalism.  And if you included a rule
to allowed VPs to omit the verb, you would erroneously accept

The chef Edgar sushi and served Edna jambalaya

unless you somehow conditioned the deletion on the context (e.g. only
allowed deletion in the second and subsequent clauses), which is
also not within the scope of context-free grammars.

4.4.b

The dependencies are:

the mouse[1] that the cat[2] that the dog chased[2] bit[1] died

where a noun-verb pair with the same number indicates a verb-object
relationship.  You could also have

the mouse[1] that the cat[2] that the dog[3] chased[3] bit[2] died[1]

where a numbered pair indicates a verb-subject relationship.

For the other sentence, the dependencies could be either of:

Verb-object:

John saw[1] the dog[1] that chased[2] the cat[2] that bit[3] the
mouse[3] that died.

Verb-subject:

John[1] saw[1] the dog[2] that chased[2] the cat[3] that bit[3]
the mouse[4] that died[4].

Assuming the human sentence processor was something like the
bottom-up or left-corner stack based parsers we've discussed in
class, processing the first sentence requires storing an incomplete
noun on the stack while all the intervening material is processed,
until you get to the verb it belongs with.  On the other hand, in the
second sentence there is only a small, fixed amount of material
intervening in between the noun and the verb it belongs with.

```