# Determinization and Minimization of Automata for Nested Words Revisited
## 3 Nested Regular Expressions
### Compilation of NREs to NWAs  
We next discuss a compiler from _NREs_\(E\) to _NWAs_\(nwa(E)\). This compiler extends on the McNaughton-Yamada-Thompson algorithm [36] for regular expressions, which introduces epsilon edges for constructing the automata of composition \(E\cdot E^{\prime}\). Figure 7: The _NWA_\(\mathcal{T}\) maps top level positions to state 0 and nested positions to 1 or 1\({}^{\prime}\). **Theorem 1**. : _For any NRE \(E\), we can construct an NWA \(A\) such that \(L(A)=L(E)\). If \(E\) contains neither conjunctions nor negations, then the construction is in time \(O(|E|)\)._  
Proof sketch. : Conjunctions \(E\&E^{\prime}\) are compiled to products of automata, so repeated conjunctions may lead to an exponential blow up. Negations \(\overline{E}\) are computed by complementing automata based on determinization. Each complementation may lead to an exponential blow-up, so when this is repeated, the construction may become non-elementary. For expressions without conjunction and negation, no such blow-up may arise. As stated by the theorem, we have to show that expressions can be compiled in linear time. **Case \(E=E^{\prime}\cdot E^{\prime\prime}\):**: We use the McNaughton-Yamada-Thompson algorithm for composing the _NWA_s of \(nwa(E^{\prime})\) and \(nwa(E^{\prime\prime})\). **Case \(E=\langle E^{\prime}\rangle\):**: Let \(Q^{\prime}_{h}\), \(Q^{\prime}_{t}\), and \(\Gamma^{\prime}\) be, respectively, the set of hedge states, tree states, and stack symbols of \(nwa(E^{\prime})\). We consider new hedge states \(q_{i}\) and \(q_{f}\) that are not in \(Q^{\prime}_{h}\), a new tree state \(p\) not in \(Q^{\prime}_{t}\) and a new stack symbol \(\gamma\) not in \(\Gamma^{\prime}\). Then, \(nwa(E)\) is constructed by adding to \(nwa(E^{\prime})\) opening rules \(q_{i}\xrightarrow{\downarrow\gamma}q\) for all the initial states \(q\) of \(nwa(E^{\prime})\), tree rules \(q^{\prime}\dashrightarrow p\) for all the final states \(q^{\prime}\) of \(nwa(E^{\prime})\) and a closing rule \(p\xrightarrow{\uparrow\gamma}q_{f}\). Furthermore, we set \(q_{i}\) as the only initial state of \(nwa(E)\), and \(q_{f}\) as its sole final state. **Case \(E=\mu a.E^{\prime}\):**: Special care has to be given to repeat expression \(\mu a.E\). First of all, the naive compilation approach for these expression turns out to be wrong. Second, fixing the problem in the simplest possible manner does not lead to a linear time algorithm. Note that we can assume w.l.o.g. that \(a\) occurs at most once in \(E\) by using the golden lemma of the \(\mu\) calculus [37], stating for all names \(a_{1},\dots,a_{n}\) and expressions \(E^{\prime\prime}\) in which \(a_{1},\dots,a_{n}\) can appear free that \(\mu a_{1},\dots\dots\mu a_{n}\). \(E^{\prime\prime}\equiv\mu a.E^{\prime\prime}[a_{1}/a,\dots,a_{n}/a]\). Our construction guarantees that all transitions of the form \(q\xrightarrow{a}q^{\prime}\) in \(nwa(E)\) will start with the same state \(q\). The wrong naive construction would remove the transitions \(q\xrightarrow{a}q^{\prime}\) from \(nwa(E)\) and add \(\varepsilon\)-rules from \(q\) to all the initial states of \(nwa(E)\), and from all final states of \(nwa(E)\) to \(q^{\prime}\). Unfortunately, the construction is not correct. For illustration, we consider the _NRE \(E=\mu a.\langle a^{*}\rangle\)_. The reader should be warned that constructing an _NWA_ for \(E\) is less trivial than it might seem at first sight. One has to start from the _NWA_ for \(\langle a^{*}\rangle\) which is given in Figure 8.  
Simply adding epsilon edges to capture the operator \(\mu a\) will not work though. It will lead to the wrong automaton in Figure 9. This automaton will wrongly accept the hedge \(\langle\rangle\langle\rangle\), as this hedge does not belong to \(L(E)\). If the _NWA_ for \(E\) is multi-module, then the naive construction of compiling \(\mu a.E\) can be made correct. Therefore, the simplest fix is to make the _NWA_ multi-moduled, before applying the naive construction.