ha1, . . . , ai−1, Bi,j , C, γi = ha1, . . . , ai−1, Bi,j , βi. Then, Γ(p(root, D**)) =** γ, because i − 1 < i and Γ(p(D, Bi,j **)) =** hCi, because the node Bi,j is the left child of AND-NODE that corresponds to the production D → C, Bi,j . Therefore, Γ(p(root, Bi,j )) = h**C, γ**i = β. This leads to a contradiction.

⊓⊔
Example 5. An example of the mapping described in the last proof is in Figure 4(a) for the grammar of our running example. Consider the OR-NODE A1,1. There are 2 paths from S1,3 to A1,1. One is direct and uses only OR-NODES hS1,3, A1,1i and the other uses OR-NODES hS1,3, A1,2, A1,1i. The 2 paths are mapped to 2 different stack configurationshA1,1, B2,2i and hA1,1, A2,1, B3,1irespectively. We highlight edges that are incident to AND-NODES on each path and lead to the right children of these AND-NODES.

There is exactly one such edge for each element of a stack configuration. ⊓⊔
Note that theorem 1 only specifies a surjection from paths to stack configurations, not a bijection. Indeed, different paths may produce the same configuration Γ.

Example 6. Consider the grammar G = {S → AA, A → a|AA|BC, B → b|**BB, C** →
c|CC} and the AND/OR graph of this grammar for a string of length 5. The path hS1,5, A2,4, B2,2i uses the productions S1,5 → A1,1A2,4 and A2,4 → B2,2C4,2, while the path hS1,5, A3,3, B3,1i uses the productionsS1,5 → A1,2A3,3 and A3,3 → B3,1C4,2. Both paths map to the same stack configuration hC4,2i. ⊓⊔
By construction, the resulting NFA has one state for each stack configuration of the PDA in parsing a string. Since each path corresponds to a stack configuration, the number of states of the NFA before applying ε-closure is bounded by the number of paths from the root to any OR-NODE in the AND/OR graph. This is cheap to compute using the following recursive algorithm [6]:

$$P D(v)=\left\{\begin{array}{l}{{1}}\\ {{\sum_{p}P D(p)}}\end{array}\right.$$
$$\mathbf{t}\mathbf{s}$$
$$(1)$$

P D(v) = 1PIf v has no incoming edges
p P D(p) where p is a parent of v(1)
Therefore, the number of states of the NFA Na is at most Pv P D(v), where v is an OR-NODE of Ga (Figure 4).

We can compute the exact number of paths in Na before ε-closure without constructing the NFA by counting paths in the *stack graph* Gv for each OR-NODE v. The stack graph captures the observation that each element of a stack configuration generated from a path p is associated with exactly one edge e that is incident on p and leads to the right child of an AND-NODE. Gv contains one path for each sequence of such edges, so that if two paths p and p
′in Ga are mapped to the same stack configuration, they are also mapped to the same path in Gv. Formally, the stack graph of an OR-NODE
v ∈ V (Ga) is a DAG Gv, such that for every stack configuration Γ of Pa with k elements, there is exactly one path p in Gv of length k and v
′is the i th vertex of p if and only if v
′is the i th element from the top of Γ.

Example 7. Consider the grammar of the running example and the OR-NODE A1,1 in the AND/OR graph. The stack graph GA1,1 for this OR-NODE is shown in figure 4(b).