Linguistics 484 - Grammars Ling484 Notes A. C. Brett acbrett@uvic.ca
Department of Linguistics
University of Victoria
Clearihue C139
Last updated: 24 March 2001

Push-Down Automaton: Embedded Constituent Processing

This page illustrates the reductions performed by a push-down automaton to accept sentences with embedded constituents. A character format tree shows the structure of the sentence that is being processed by the machine. Note that determiners, in the case of the English sentences, and the case-marking particles, in the Japanese sentence, have been combined with the nouns thereby forming a single symbol in order to simplify processing and to clarify its presentation.

Centre-Embedded English Sentence. 

                               s
                 ------------------------------
                 np                           vp
     -------------------------                |
     np                      s               ran
     |              --------------------
  the_cat           np                 vp
              --------------           |
              np           s         chased
              |        ----------
           the_dog     np       vp
                       |        |
                    the_girl  owned


   <[#], $, [the_cat,the_dog,the_girl,owned,chased,ran]>
=> <[#], np, [the_dog,the_girl,owned,chased,ran]>
=> <[#,np], np, [the_girl,owned,chased,ran]>
=> <[#,np,np], np, [owned,chased,ran]>
=> <[#,np,np,np], vp, [chased,ran]>
=> <[#,np,np], s, [chased,ran]>
=> <[#,np], np, [chased,ran]>
=> <[#,np,np], vp, [ran]>
=> <[#,np], s, [ran]>
=> <[#], np, [ran]>
=> <[#,np], vp, []>
=> <[#], s, []>

Right-Branching English Sentence. 

          s
    --------------
    np           vp
    |      --------------
  a_cat    v            np
           |       ------------
         killed    np         s
                   |     ------------
                 a_rat  relp        vp
                         |     ------------
                        that   v          np
                               |     ------------
                              ate    np         s
                                     |      ----------
                                   cheese  relp      vp
                                            |     -------
                                           that   be   adj
                                                  |     |
                                                 was  rotten


   <[#], $, [a_cat,killed,a_rat,that,ate,cheese,that,was,rotten]>
=> <[#], np, [killed,a_rat,that,ate,cheese,that,was,rotten]>
=> <[#,np], v, [a_rat,that,ate,cheese,that,was,rotten]>
=> <[#,np,v], np, [that,ate,cheese,that,was,rotten]>
=> <[#,np,v,np], relp, [ate,cheese,that,was,rotten]>
=> <[#,np,v,np,relp], v, [cheese,that,was,rotten]>
=> <[#,np,v,np,relp,v], np, [that,was,rotten]>
=> <[#,np,v,np,relp,v,np], relp, [was,rotten]>
=> <[#,np,v,np,relp,v,np,relp], be, [rotten]>
=> <[#,np,v,np,relp,v,np,relp,be], adj, []>
=> <[#,np,v,np,relp,v,np,relp], vp, []>
=> <[#,np,v,np,relp,v,np], s, []>
=> <[#,np,v,np,relp,v], np, []>
=> <[#,np,v,np,relp], vp, []>
=> <[#,np,v,np], s, []>
=> <[#,np,v], np, []>
=> <[#,np], vp, []>
=> <[#], s, []>

Left-Branching Japanese Sentence. 

                                            s
                                  ----------------------
                                  np                   vp
                         -------------------           |
                         s                 np     kusatte-ita
                 ------------------        |
                 np               vp    tiizu_wa
         -----------------        |
         s               np     tabeta
     ----------          |
     np       vp     nezumi_ga
     |        |
  neko_ga  korosita


   <[#], $, [neko_ga,korosita,nezumi_ga,tabeta,tiizu_wa,kusatte-ita]>
=> <[#], np, [korosita,nezumi_ga,tabeta,tiizu_wa,kusatte-ita]>
=> <[#,np], vp, [nezumi_ga,tabeta,tiizu_wa,kusatte-ita]>
=> <[#], s, [nezumi_ga,tabeta,tiizu_wa,kusatte-ita]>
=> <[#,s], np, [tabeta,tiizu_wa,kusatte-ita]>
=> <[#], np, [tabeta,tiizu_wa,kusatte-ita]>
=> <[#,np], vp, [tiizu_wa,kusatte-ita]>
=> <[#], s, [tiizu_wa,kusatte-ita]>
=> <[#,s], np, [kusatte-ita]>
=> <[#], np, [kusatte-ita]>
=> <[#,np], vp, []>
=> <[#], s, []>

Linguistics 484 Notes Index Top of Page