Annotated word-graph

An annotated word-graph is a word-graph annotated with the results of the parser. Such an annotated word-graph is defined with respect to an input word-graph (given by the functions $\mbox{\it trans\/}$ and $\mbox{\it final\/}$) and with respect to the results of parsing (given by the function $\mbox{\it parsed\/}$).

The annotated word-graph is a directed acyclic graph (V,E) where

• V is the set of vertices consisting of the states of the word-graph $v_0\dots v_n$, and a new vertex v_n+1. v₀ is the start state. v_n+1 is the final state.
• E is the set of edges consisting of:
  1. skip edges. For all $\mbox{\it trans\/}(v_i,v_j,w,a)$ there are edges $(v_i,v_j,w,a,\epsilon)$.
  2. category edges. For all $\mbox{\it parsed\/}(v_i,v_j,x,a,q)$ there are edges (v_i,v_j,x,a,q).
  3. stopping edges. For all $\mbox{final}(v_i,a)$ there are edges $(v_i,v_{n+1},\epsilon,a,\epsilon)$.