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.
Return to the course home page.