Summary: Recently, Yamamoto presented a new method for the conversion from regular expressions (REs) to non-deterministic finite automata (NFA) based on the Thompson \({\epsilon} \)-NFA (\(\mathcal {A}_{\mathsf {T}}\)). The \(\mathcal {A}_{\mathsf {T}}\) automaton has two quotients discussed: the suffix automaton \(\mathcal {A}_{\mathsf {suf}}\) and the prefix automaton, \(\mathcal {A}_{\mathsf {pre}}\). Eliminating \(\epsilon\)-transitions in \(\mathcal {A}_{\mathsf {T}}\), the Glushkov automaton (\(\mathcal {A}_{\mathsf {pos}}\)) is obtained. Thus, it is easy to see that \(\mathcal {A}_{\mathsf {suf}}\) and the partial derivative automaton (\(\mathcal {A}_{\mathsf {pd}})\) are the same. In this paper, we characterise the \(\mathcal {A}_{\mathsf {pre}}\) automaton as a solution of a system of left RE equations and express it as a quotient of \(\mathcal {A}_{\mathsf {pos}}\) by a specific left-invariant equivalence relation. We define and characterise the right-partial derivative automaton (\(\overleftarrow{\mathcal {A}}_{\mathsf {pd}}\)). Finally, we study the average size of all these constructions both experimentally and from an analytic combinatorics point of view.
For the entire collection see [Zbl 1314.68011].