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,
you should definitely READ all four problems and also read the
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

      we added the rules      

	  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?