Here's another invalid parse, this one using the modified items and inference rules we cooked up to fix the last one. This would still be a problem using our initial inference rules, though. This one is a parse of the string aabbbecc.
1) [a,0,*,*,1,*] (A1)
2) [a,1,*,*,2,*] (A1)
3) [b,2,*,*,3,*] (A1)
4) [b,3,*,*,4,*] (A1)
5) [b,4,*,*,5,*] (A1)
6) [e,5,*,*,6,*] (A1)
7) [c,6,*,*,7,*] (A1)
8) [c,7,*,*,8,*] (A1)
9) [S,*,*,*,*,*] (A2)
10) [X,*,*,*,*,*] (A2)
11) [Y,*,*,*,*,*] (A2)
The next two items are used later but don't appear in a properly formed parse tree using only the local trees:
12) [S,4,5,*,*,3] (I2,5,9)
13) [Y,4,5,*,*,*] (I13,11,12)
Back to the "core" parse tree:
14) [S,2,3,*,*,3] (I2,3,9)
15) [Y,2,3,*,*,*] (I13,11,14)
16) [S,2,3,7,8,2] (I4,15,8)
17) [X,2,3,7,8,*] (I13,10,16)
18) [S,1,3,7,8,1] (I1,2,17)
19) [S,3,4,*,*,3] (I2,4,9)
20) [S,1,4,7,8,3] (I10,18,19)
Here is where item 13 comes into play, inserting the b from the "rogue" subtree:
21) [Y,1,5,7,8,*] (I10,13,20)
22) [S,1,5,6,8,2] (I3,7,21)
23) [X,1,5,6,8,*] (I13,10,22)
24) [S,0,5,6,8,1] (I1,1,23)
25) [S,5,*,*,6,0] (I5,6)
26) [S,0,*,*,8,0] (I6,24,25)
27) [S,0,*,*,8,*] (I13,9,26)
The problem here is that the inference rule allows us to build a nonsense tree where a Y either has two 3-dimensional successors or both a 3-dimensional successor and a 2-dimensional successor. The former is impossible, and the latter is also impossible because Y always occurs in the foot of a local tree. I10 is a necessary inference rule, however, since it was designed for the case where the node has both a 3-dimensional and a 2-dimensional successor, i.e. it is the root of its local tree.
Posted by kellyia at June 15, 2004 05:39 PM