Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Prefix and Right-Partial Derivative Automata
verfasst von : Eva Maia, Nelma Moreira, Rogério Reis
Erschienen in: Evolving Computability
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 (\(\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 \(\varepsilon \)-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.