Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Partial Derivatives of an Extended Regular Expression
verfasst von : Pascal Caron, Jean-Marc Champarnaud, Ludovic Mignot
Erschienen in: Language and Automata Theory and Applications
Verlag: Springer Berlin Heidelberg
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
The notion of expression derivative due to Brzozowski leads to the construction of a deterministic automaton from an extended regular expression, whereas the notion of partial derivative due to Antimirov leads to the construction of a non-deterministic automaton from a simple regular expression. In this paper, we generalize Antimirov partial derivatives to regular expressions extended to complementation and intersection. For a simple regular expression with
n
symbols, Antimirov automaton has at most
n
+ 1 states. As far as an extended regular expression is concerned, we show that the number of states can be exponential.