A general framework for the derivation of regular expressions

DOI10.1051/ITA/2014010MaRDI QIDQ2874638zbMATH OpenOpenAlexFDO

Authors Pascal Caron, Ludovic Mignot, Jean-Marc Champarnaud

Publication date 8 August 2014

Published in RAIRO. Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.5003

zbMATH Keywords

alternating automataderivationpartial derivationregular expressions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: The aim of this paper is to design a theoretical framework that allows us to perform the computation of regular expression derivatives through a space of generic structures. Thanks to this formalism, the main properties of regular expression derivation, such as the finiteness of the set of derivatives, need only be stated and proved one time, at the top level. Moreover, it is shown how to construct an alternating automaton associated with the derivation of a regular expression in this general framework. Finally, Brzozowski's derivation and Antimirov's derivation turn out to be a particular case of this general scheme and it is shown how to construct a DFA, a NFA and an AFA for both of these derivations.

Recommendations

• Partial derivatives of regular expressions and finite automata constructions
• Partial derivatives of regular expressions and finite automaton constructions
• scientific article; zbMATH DE number 1773077
• Regular-expression derivatives re-examined
• Canonical derivatives, partial derivatives and finite automaton constructions.

Cited in

(12)

• A benchmark production tool for regular expressions
• Derivatives for regular shuffle expressions
• Position automaton construction for regular expressions with intersection
• On the state complexity of partial derivative automata for regular expressions with intersection
• Derivatives for Enhanced Regular Expressions
• Polynomial functors constrained by regular expressions
• Partial derivatives for context-free languages. From -regular expressions to pushdown automata
• Bottom-Up derivatives of tree expressions
• scientific article; zbMATH DE number 3271521 (Why is no real title available?)
• Monadic Expressions and Their Derivatives
• Monadic expressions and their derivatives
• Relations between equation automata and follow automata

This page was built for publication: A general framework for the derivation of regular expressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874638)