Position Automata for Semi-extended Expressions
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis · Journal of automata, languages and combinatorics · 2018
Positions and derivatives are two essential notions in the conversion methods from regular expressions to equivalent finite automata. Partial derivative based methods have recently been extended to regular expressions with intersection (semi-extended). In this paper, we present a position automaton construction for those expressions. This construction generalizes the notion of position, making it compatible with intersection. The resulting automaton is homogeneous and has the partial derivative automaton as a quotient.