Recently, Yamamoto presented a new method for the conversion from regular expressions (REs) to non-deterministic finite automata (NFA) based on the Thompson $\varepsilon$-NFA ($\at$). The $\at$ automaton has two quotients discussed: the suffix automaton $\asuf$ and the prefix automaton, $\apre$. Eliminating $\varepsilon$-transitions in $\at$, the Glushkov automaton ($\mathcal{A}_{pos}$) is obtained. Thus, it is easy to see that $\asuf$ and the partial derivative automaton ($\apd)$ are the same. In this paper, we characterise the $\apre$ automaton as a solution of a system of left RE equations and express it as a quotient of $\mathcal{A}_{pos}$ by a specific left-invariant equivalence relation. We define and characterise the right-partial derivative automaton ($\apdr$). Finally, we study the average size of all these constructions both experimentally and from an analytic combinatorics point of view.
Prefix and Right-Partial Derivative Automata.
Eva Maia (FCUP/CMUP)