The Prefix Automaton
Sabine Broda, Eva Maia, Nelma Moreira, Rogério Reis · Journal of automata, languages and combinatorics · 2021
There are many different constructions when converting regular expressions to finite automata. In this paper we focus on the prefix automaton, $\apre$, introduced by Yamamoto in 2014. We present two different methods for the construction of $\apre$. First, an inductive one, based on a system of expression equations. A second one using an iterative function for computing the states and transitions. We establish relationships between $\apre$ and other constructions, such as the position automaton, partial derivative automaton and their double reversal (dual) counterparts. We study the average size of these constructions, both experimentally and from an analytic combinatorics point of view. Finally, we extend the construction of the prefix automaton to regular expressions with intersection and show that the relationships with the other automaton constructions also hold for these expressions.