state is hS1,ni corresponding to the initial stack hS1,ni of Pa. Algorithm 2 unfolds the PDA in a similar way to unfolding the DFA. Note that the NFA accepts only strings of length n and has the initial state Q0 = hS1,ni and the single final state F0 = hi.

![0_image_0.png](0_image_0.png)

We start from the initial stack hS1,ni and find all distinct stack configurations that are reachable from this stack using transitions from Pa. For each reachable stack configuration we create a state in the NFA and add the corresponding transitions. If the new stack configurations are the result of expansion of a production in the original grammar, these transitions are ε−transitions, otherwise they consume a symbol from the input string. Note that if a non-terminal appears on top of the stack and gets replaced, then it cannot appear in any future stack configuration due to the acyclicity of Ga. Therefore |α| is bounded by O(n) and Algorithm 2 terminates. The size of Na is O(|Ga| n)
in the worst case. The automaton Na that we obtain before line 21 is an acyclic NFA
with ε transitions. It accepts the same language as the PDA Pa since every path between the starting and the final state of NA is a trace of the stack configurations of Pa.

Figure 3(a) shows the automaton Na with ε-transitions constructed from the running example. After applying the ε-closure operation, we obtain a layered NFA that does not have ε transitions (line 21) (Figure 3(b)).

## 4.4 Computing The Size Of The Nfa

As the NFA may be exponential in size, we provide a polynomial method of computing its size in advance. We can use this to decide if it is practical to transform it in this way. Observe first that the transformation of a PDA to an NFA maintains a queue of states that correspond to stack configurations. Each state corresponds to an OR-NODE in the AND/OR graph and each state of an OR-NODE v is generated from the states of the