CykParse: Simple example Grammar (Chomsky normal form) 1. S -> Noun VP [1.0] 2. VP -> Verb Noun [0.5] 3. VP -> Modal Verb [0.5] 4. Modal -> can [1] 5. Noun -> can [0.3] 6. Noun -> fish [0.3] 7. Noun -> people [0.4] 8. Verb -> can [0.1] 9. Verb -> fish [0.8] 8. Verb -> people [0.1] Iterations of line 5 Create the following trees nodes (leaves) i = 1 A. [Noun | 1 | 1 | people | --- | --- | 0.4] B. [Verb | 1 | 1 | people | --- | --- | 0.1] i = 2 C. [Modal | 2 | 2 | can | --- | --- | 1 ] D. [Noun | 2 | 2 | can | --- | --- | 0.3 ] E. [Verb | 2 | 2 | can | --- | --- | 0.1 ] i=3 F. [Noun | 3 | 3 | fish | --- | --- | 0.3 ] G. [Verb | 3 | 3 | fish | --- | --- | 0.8 ] Main loop (I show only iterations that create a node of non-zero probability) length = 2 i = 1 j = 2 M = VP Create node H. [VP | 1 | 2 | --- | --- | --- | 0.0] k = 1 Rule = VP -> Verb Noun [0.5] Combination of B & D and prob. of rule has probability 0.015. Change H to be [VP | 1 | 2 | --- | B | D | 0.015] i = 2 j = 3 M = VP Create node I. [VP | 2 | 3 | --- | --- | --- | 0.0] k = 2 Rule = VP -> Verb Noun [0.5] Combination of E & F and prob of rule has probability 0.015. Change I to be [VP | 2 | 3 | --- | E | F | 0.03] Rule = VP -> Modal Verb [0.5] Combination of C & G and prob of rule has probability 0.4. Change I to be [VP | 2 | 3 | --- | C | G | 0.4] length = 3 i = 1 j = 3 M=S Create node J. [S | 1 | 3 | --- | --- | --- | 0.0] k = 1. Rule = S -> Noun VP [1.0] Combination of A & I and prob. of rule has probability 0.16 Change J to be [S | 1 | 3 | --- | A | I | 0.16] Done. Final Tree: S Noun people VP Modal can Verb fish