Technical Report: DCC-2014-09

Left Relations

Eva Maia, Nelma Moreira, Rogério Reis

DCC \& CMUP, Faculdade de Ciências da Universidade do Porto
R. Campo Alegre 687, 4169-007 Porto, Portugal
e-mail: emaia@dcc.fc.up.pt,nam@dcc.fc.up.pt,rvr@dcc.fc.up.pt
December 2014

Abstract

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 (At). The At automaton has two quotients considered: the suffix automaton Asuf and the prefix automaton, Apre. Eliminating epsilon-transitions in At, the Glushkov automaton (Apos) 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 apos 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.