# Efficient Construction of the Equation Automaton
## 5 Efficient Conversion Algorithm
### Computation of Transitions and Final States  
After merging \(\equiv_{e}\)-equivalent states in the previous step, we obtain a reduced automaton \(C_{\equiv_{e}}(Id(\mathcal{T}_{\mathrm{E}}))\) having the same set of states as the equation automaton. To compute the transition function, we first enable the cyclic transitions previously disabled in the case when \(\mathrm{E}=\mathrm{F}^{*}\) on \(C_{\equiv_{e}}(Id(\mathcal{T}_{\mathrm{E}}))\).  
Let \(Q_{\equiv_{e}}\) be the set of states of \(C_{\equiv_{e}}(Id(\mathcal{T}_{\mathrm{E}}))\). Recall that epsilon removal operation is denoted by, \(rneps(p)\) for a state \(p\in Q\) and \(rneps(\mathcal{A})\) denotes the resulted automaton after removing marked and non-marked \(e\)-transitions from the automaton \(\mathcal{A}\).  
As a consequence of Lemma 5 from [8], the following Lemma yeilds.  
**Lemma 2**: _(Lemma 5 in [8]). Let \(q\) and \(q^{\prime}\) be two position states in \(Q_{\equiv_{e}}\) associated respectively with the positions \(x\) and \(x^{\prime}\) in \(\mathrm{pos}(\mathrm{E})\cup\{0\}\), we have:_  
\[q\in rmeps(q^{\prime})\text{ iff }h(c_{x}(\mathrm{E}))\in\partial_{a}(h(c_{x^{ \prime}}(\mathrm{E})))\text{, for some }a\in A_{\mathrm{E}}.\]The set of destination states of the outgoing transitions from a state \(q\in Q_{\equiv_{e}}\) is then equal to  
\[\{p\in Q_{\equiv_{e}}\mid p\in\mathit{rmeps}(q)\text{ and }p\text{ is a position state}\}\]  
**Lemma 3**.: _Let \(q\) be a position state in \(Q_{\equiv_{e}}\) associated with a position \(x\) in \(\mathrm{pos}(\mathrm{E})\cup\{0\}\), we have:_  
\[F\in\mathit{rmeps}(q)\text{ iff }\lambda(c_{x}(\mathrm{E}))=1.\]  
**Proposition 9**.: _We have \(\mathcal{E}_{\mathrm{E}}=\mathit{rmeps}(C_{\equiv_{e}}(\mathit{Id}(\mathcal{ T}_{\mathrm{E}})))\)_  
**Example 8**.: _(Continues). Let us consider the automaton \(C_{\equiv_{e}}(\mathit{Id}(\mathcal{T}_{\mathrm{E}}))\) of the Example 7. The final states and the transitions of the equation automaton are computed over \(C_{\equiv_{e}}(\mathit{Id}(\mathcal{T}_{\mathrm{E}}))\) using epsilon removal operation \(\mathit{rmeps}\) as follows:_  
* _The set of states of the equation automaton are_ \(\{0,\{5,8,11\},16\}\)_._
* _Since the final state of_ \(C_{\equiv_{e}}(\mathit{Id}(\mathcal{T}_{\mathrm{E}}))\) _is the state_ \(19\) _and_ \(19\in\mathit{rmeps}(0),19\in\mathit{rmeps}(\{5,8,11\})\)_, and_ \(19\in\mathit{rmeps}(16)\)_, then the set of final states are_ \(\{0,\{5,8,11\},16\}\)_._
* _There are two paths in_ \(C_{\equiv_{e}}(\mathit{Id}(\mathcal{T}_{\mathrm{E}}))\) _from the state_ \(0\) _to the state_ \(\{5,8,11\}\) _labeled respectively by_ \(\varepsilon\cdot\varepsilon\cdot\varepsilon\cdot\varepsilon\cdot a\) _and_ \(\varepsilon\cdot\varepsilon\cdot\varepsilon\cdot b\)_, then_ \(\{5,8,11\}\in\mathit{rmeps}(0)\)_. Consequently, two transitions_ \((0,a,\{5,8,11\})\) _and_ \((0,b,\{5,8,11\})\) _are added to the equation automaton. The same process will be applied for other transitions._  
Since there are \(O(\mid\mathrm{E}\mid)\) states in \(C_{\equiv_{e}}(\mathit{Id}(\mathcal{T}_{\mathrm{E}}))\) and the operation \(\mathit{rmeps}(C_{\equiv_{e}}(\mathit{Id}(\mathcal{T}_{\mathrm{E}})))\) is performed on exactly \(|Q_{\equiv_{e}}|\) states, the following theorem holds.  
**Theorem 6**.: _Let \(\mathrm{E}\) be a regular expression. The equation automaton of \(\mathrm{E}\) can be computed in \(O(\mid\mathrm{E}\mid\cdot|Q_{\equiv_{e}}|)\)._