# Efficient Construction of the Equation Automaton
## 2 Preliminaries
### Regular Expressions and Finite Automata
#### 2.1.1 Regular Expressions and Languages  
A regular expression over the alphabet \(A\) is a term of the algebra \(\mathcal{T}_{reg(A)}\) defined over the set \(A\cup\{0,1\}\) with the symbols of functions \(*,+,\cdot\), where \(*\) is unary and \(+\) and \(\cdot\) are binary. Properties of the constants \(0,1\) and the operators \(*,+,\) and \(\cdot\) lead to identities on this algebra. Each regular expression denotes a language. L is the function that assigns to each regular expression the regular language it denotes. L : \(T_{reg(A)}\longrightarrow reg(A^{*})\) is defined as follows:  
\[L(0) = \emptyset\] \[L(1) = \{\varepsilon\}\] \[L(a) = a,\text{ for each }a\text{ in }A\] \[L(\text{F}+\text{G}) = L(\text{F})\cup L(\text{G})\] \[L(\text{F}\cdot\text{G}) = L(\text{F})L(\text{G})\] \[L(\text{F}^{*}) = L(\text{F})^{*}\]The following identities are classically used:  
\[0+\mathrm{E}=\mathrm{E}=\mathrm{E}+0,\ \ 1\cdot\mathrm{E}=\mathrm{E}=\mathrm{E} \cdot 1,\ \ 0\cdot\mathrm{E}=0=\mathrm{E}\cdot 0.\]  
Let \(\mathrm{E}\) be a regular expression. The set of letters occurring in \(\mathrm{E}\) is denoted by \(A_{\mathrm{E}}\). To specify their position in the expression, letters are subscripted following the order of reading. The resulted expression is _the linearized form_ of \(\mathrm{E}\), denoted by \(\overline{\mathrm{E}}\). For example, starting from \(\mathrm{E}=(a+b)^{*}aba+1\), one obtains the linearized version \(\overline{\mathrm{E}}=(a_{1}+b_{2})^{*}a_{3}b_{4}a_{5}+1\) of \(\mathrm{E}\). The subscripted letters are called _positions_; the set of all position in the expression \(\mathrm{E}\) is denoted by \(\mathrm{pos}(\mathrm{E})\). For the previous example, we have \(\mathrm{pos}(\mathrm{E})=\{a_{1},b_{2},a_{3},b_{4},a_{5}\}\). If \(\mathrm{F}\) is a subexpression of \(\mathrm{E}\), we denote by \(\mathrm{pos}_{\mathrm{E}}(\mathrm{F})\) the subset of positions \(\mathrm{E}\) that are letters of \(\mathrm{F}\). We say that a regular expression is in linear form if each letter of the expression occurs only once. We denote by \(h\) the function that maps each position in \(\mathrm{pos}(\mathrm{E})\) to the letter of \(A_{\mathrm{E}}\) that appears at this position in \(\mathrm{E}\). For \(\mathrm{E}=(a+b)^{*}aba+1\), we have \(h(a_{1})=h(a_{3})=h(a_{5})=a\) and \(h(b_{2})=h(b_{4})=b\). The _size_ of the regular expression \(\mathrm{E}\), denoted by \(|\,\mathrm{E}\,|\), is the number of nodes in its syntax tree. We call _alphabetic width_ of \(\mathrm{E}\), denoted by \(||\,\mathrm{E}\,||\), the number of occurrences of letters in the expression i.e., the cardinality of \(\mathrm{pos}(\mathrm{E})\). The alphabetic width of the expression \((a+b)^{*}aba+1\) is equal to \(5\); its size is equal to \(12\). Notice that the alphabetic width and the size of a regular expression are independent parameters. Therefore complexities are expressed w.r.t. both of these two parameters. However, it is usual to preprocess the input expression in order to reduce its size and to make its size proportional to its alphabetic width. So, if we consider a reduced regular expression \(\mathrm{E}\) w.r.t. the following rules:  
* \(1+1=1\),
* \(1+\mathrm{E}+1=1+\mathrm{E}\),
* \(\mathrm{E}\) is in Star-Normal Form (SNF) [16]. Thus, we have in this case \(|\,\mathrm{E}\,|=O(||\,\mathrm{E}\,||)\). It is known that regular expressions can be transformed to SNF in linear time [16]. \(\lambda(\mathrm{E})\) denote the null term of \(\mathrm{E}\), that is  
\[\lambda(\mathrm{E})=\left\{ \begin{array}{ll}1&\text{if $\varepsilon\in \mathrm{L}(\mathrm{E})$,}\\ 0&\text{otherwise.}\end{array} \right.\]  
By \(T(\mathrm{E})\) we denote the syntax tree associated with the regular expression \(\mathrm{E}\). A node in \(T(\mathrm{E})\) will be denoted by \(\
u\). We write \(\mathit{Nodes}(\mathrm{E})\) for the set of nodes of \(T(\mathrm{E})\).