# Efficient Construction of the Equation Automaton
## 5 Efficient Conversion Algorithm  
In this section, we will show that the equation automaton \(\mathcal{E}_{\rm E}\) of a regular expression \(\rm E\) can be deduced from the associated Thompson automaton in \(O(|\,\rm E\,|\cdot|Q_{\equiv_{\varepsilon}}|)\) time, where \(|Q_{\equiv_{\varepsilon}}|\) denotes the number of states of \(\mathcal{E}_{\rm E}\). Algorithm 1 summarizes the different steps of our approach.  
```
input : The [PERSON] automaton \(\mathcal{T}_{\rm E}=\langle Q,A_{\rm E},I,\delta,F\rangle\) associated with a regular expression \(\rm E\). output : The equation automaton \(\mathcal{E}_{\rm E}\) associated with \(\rm E\). /* Computation of states */  Compute \(Id(\mathcal{T}_{\rm E})\): Subexpressions identification over \(\it states\) of \(\mathcal{T}_{\rm E}\). * Define the sub-automaton \(Id(\mathcal{T}_{\rm E})\) by marking recursively some \(\varepsilon\)-transitions of \(\mathcal{T}_{\rm E}\) according to the following rules: if \(\rm E=F+G\)then  mark the \(\varepsilon\)-transitions by \(\varepsilon_{l+}\) (resp. \(\varepsilon_{r+}\)) from the initial state \(I\) to \(I_{\mathcal{T}_{\rm E}}\) (resp. \(I_{\mathcal{T}_{\rm C}}\)) if\(\rm E=F^{*}\)then - mark the \(\varepsilon\)-transitions by \(\varepsilon_{*}^{1}\) from the initial state \(I\) (resp. the final state \(F_{\mathcal{T}_{\rm F}}\)) to \(I_{\mathcal{T}_{\rm F}}\) (resp. \(F\)) and by \(\varepsilon_{*}^{2}\) from the initial state \(I\) to \(F\). * - temporarily disable the \(\varepsilon\)-transition from \(F_{\mathcal{T}_{\rm F}}\) to \(I_{\mathcal{T}_{\rm F}}\). * Compute the function \(N(q)\) that maps each state \(q\in Q\) to a unique integer identifying the associated subexpression \(\rm E_{q}\), if it exists.
```  
**Algorithm 1** Computation of the equation automaton.  
For convenience, we assume that the \(k\) states of a given finite automaton are identified by the integers \(1,\cdots,k\).  
From Corollary 1, the c-continuation \(c_{x}(\mathrm{E})=H_{0}\cdots H_{l}\) associated with a position \(x\) is a concatenation of distinct subexpressions \(H_{i}\) of \(\mathrm{E}\), possibly reduced to a single subexpression or to 1. In the [PERSON] automaton \(\mathcal{T}_{\mathrm{E}}\), we can associate a position \(x\) to a particular state \(q\), called _position state_ and define the associated pseudo-continuation \(\mathrm{C}(q)=N(H_{0})\cdots N(H_{l})\), where \(N(H_{i})\) denotes the integer that identify the initial state of the [PERSON] automaton \(\mathcal{T}_{H_{i}}\). So, the first step, compute \(Id(\mathcal{T}_{\mathrm{E}})\), of our algorithm consists on computing the function \(N(.)\) such that for two subexpressions \(H_{i}\) and \(H_{j}\) of \(\mathrm{E}\), we have: \(H_{i}\equiv H_{j}\Leftrightarrow N(I_{\mathcal{T}_{H_{i}}})=N(I_{\mathcal{T}_ {H_{j}}})\). This step can be done using a special marking of the \(\varepsilon\)-transitions of \(\mathcal{T}_{\mathrm{E}}\) that makes it acyclic and deterministic and such that the right languages of its states represent the structure of the corresponding subexpressions. In the next step, Compute \(\mathrm{C}_{\equiv_{\varepsilon}}(Id(\mathcal{T}_{\mathrm{E}}))\), we re-mark the \(\varepsilon\)-transitions such that the resulted automaton is acyclic and deterministic and the right language of a position state in \(Id(\mathcal{T}_{\mathrm{E}})\) represents a pseudo-continuation. After that, one can merge equivalent position states having the same right language. The final step is the computation of final states and transitions of the equation automaton using an epsilon removal operation, denoted by \(r\text{\emph{meps}}(.)\), from the resulted automaton in the previous step.  
In the next, we will show that the equation automaton \(\mathcal{E}_{\mathrm{E}}\) can be computed efficiently from the [PERSON] automaton \(\mathcal{T}_{\mathrm{E}}\) using the following operations \(r\text{\emph{meps}}(C_{\equiv_{\varepsilon}}(Id(\mathcal{T}_{\mathrm{E}})))\).