# Determinization and Minimization of Automata for Nested Words Revisited
## 6 NWAs versus SHAs
### SHAs to NWAs  
As a first step, we introduce a transformation on _SHA_s, so that for any _SHA_:  
* if \(A\) is deterministic, the transformation returns \(A\), and
* if \(A\) is nondeterministic with set of hedge states \(Q_{h}\) and transition relation \(\Delta\), the transformation returns a new _SHA_\(A^{\prime}\) with set of hedge states \(Q^{\prime}_{h}=Q_{h}\uplus\{q_{\textit{i-init}}\}\) where \(q_{\textit{i-init}}\) is a new hedge state, and set of transitions \(\Delta^{\prime}\) which equals \(\Delta\) except that \(\langle\rangle^{\Delta^{\prime}}=\{q_{\textit{i-init}}\}\) and \(\varepsilon^{\Delta^{\prime}}=\varepsilon^{\Delta}\cup\{(q_{\textit{i-init}}, q)\mid q\in\langle\rangle^{\Delta}\}\). Then, we compile any _SHA_\(A=(Q_{h},Q_{t},\Sigma,\Lambda,I,F)\) obtained after the above transformation to an _NWA_\(nwa(A)=(Q_{h},Q_{t},\Sigma,\Gamma,\Delta^{\prime},I,F)\) such that \(L(A)=L(nwa(A))\). We set \(\Gamma=Q_{h}\), \(\_^{\Delta^{\prime}}=\_^{\Delta}\), \(a^{\Delta^{\prime}}=a^{\Delta}\) for all \(a\in\Sigma\), \(\varepsilon^{\Delta^{\prime}}=\varepsilon^{\Delta}\), \(\texttt{T}^{\Delta}=\texttt{T}^{\Delta}\):  
\[ \begin{CD}q_{1}@>{\downarrow q_{2}}>{}>\in\Delta&p\in\langle\rangle^{\Delta} \\ q_{1}@>{\downarrow q_{1}}>{}>p\in\Delta^{\prime}\text{ and }q@>{\uparrow q_{1}}>{}>q_{2}\in\Delta^{\prime}\end{CD} \]  
Clearly, if \(S\) is deterministic then so is \(nwa(S)\), as \(p\) is unique in this case in particular. One might be tempted to skip the first-step transformation and restrict the above construction rule to states \(p\) such that \(L_{q}(S|\langle\rangle^{\Delta}/\{p\})\
eq\emptyset\). However, this would lead to a huge blow-up when determinizing these _NWAs_, basically as this change spoils the single-entry property discussed in Definition 7. The conversion of step\((ch^{*}(a+b))\) in Figure 13 yields the _NWA_ in Figure 19. Note that the opening rules are deterministic (but not the whole _NWA_), as for all tree states \(q\) there is at most one hedge state \(p\) with \(\langle\rangle\to p\) such that \(q\) is accessible from \(p\). The NWA has size 64, while its determinization has size 159 (see Figure A4 of the Appendix C). The size increase raised by determinization is thus \(95=159-64\) for this _NWA_. The size increase for determinization is considerably smaller for the _NWA_ obtained from the regular expressions by indirection via a _SHA_ than for _NWAs_ obtained by direct compilation. Indeed, the determinization of \(nwa(ch^{*}(a+b))\) blows the size from 39 to 271. The size increase for the determinization of \(nwa(ch^{*}(a+b))\) is thus \(242=271-39\) while for \(nwa(\text{step}(ch^{*}(a+b)))\) it is only \(95=159-64\). The experiments will show that this is not an exception but the general rule. Intuitively, the reason is that _NWAs_ obtained from _SHA_s do all the work bottom-up, where _NWAs_ obtained directly from the regular expression do a considerable amount of work top-down. In terms of the work in [22], this restriction can be characterized syntactically by the single-entry property:  
**Definition 7**. : _A (weak) single-entry NWA \(A=(Q_{h},Q_{t},\Sigma,\Gamma,\Delta,I,F)\) is a NWA for which there exists a single state \(q_{entry}\in Q_{h}\) such that all opening rules in \(\Delta\) have the form \(q\stackrel{{\downarrow q}}{{\longrightarrow}}q_{entry}\)._  
Note that _call-driven automata_ (CDAs) discussed in [23] coincide with multi-module single-entry _dNWAs_ and also with (_multi-module) single-entry visibly pushdown automata_[22, 24]. It can be shown that \(nwa(S)\) has the (weak) single-entry property for all _SHA_s \(S\) for which the \(p\)'s are unique in the above construction rule, i.e., such that \(\left\langle\right\rangle^{\Delta}=\{p\}\). Note that this was not the case for step\((ch^{*}(a+b))\) in Figure 13 but could have been imposed w.l.o.g.