Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T09:18:21.927Z Has data issue: false hasContentIssue false

A general framework for the derivation of regularexpressions

Published online by Cambridge University Press:  27 May 2014

Pascal Caron
Affiliation:
LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France.. pascal.caron@univ-rouen.fr, jean-marc.champarnaud@univ-rouen.fr, ludovic.mignot@univ-rouen.fr
Jean-Marc Champarnaud
Affiliation:
LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France.. pascal.caron@univ-rouen.fr, jean-marc.champarnaud@univ-rouen.fr, ludovic.mignot@univ-rouen.fr
Ludovic Mignot
Affiliation:
LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France.. pascal.caron@univ-rouen.fr, jean-marc.champarnaud@univ-rouen.fr, ludovic.mignot@univ-rouen.fr

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The aim of this paper is to design a theoretical framework that allows us to perform thecomputation of regular expression derivatives through a space of generic structures.Thanks to this formalism, the main properties of regular expression derivation, such asthe finiteness of the set of derivatives, need only be stated and proved one time, at thetop level. Moreover, it is shown how to construct an alternating automaton associated withthe derivation of a regular expression in this general framework. Finally, Brzozowski’sderivation and Antimirov’s derivation turn out to be a particular case of this generalscheme and it is shown how to construct a DFA, a NFA and an AFA for both of thesederivations.