Partial derivatives of regular expressions and finite automaton constructions

Valentin Antimirov, G. Kucherov

Research output: Contribution to journalArticlepeer-review

227 Citations (Scopus)

Abstract

We introduce a notion of partial derivative of a regular expression and apply it to finite automaton constructions. The notion is a generalization of the known notion of word derivative due to Brzozowski: partial derivatives are related to non-deterministic finite automata (NFA's) in the same natural way as derivatives are related to deterministic ones (DFA's). We give a constructive definition of partial derivatives and prove several facts, in particular: (1) any derivative of a regular expression r can be represented by a finite set of partial derivatives of r; (2) the set of all partial derivatives of r is finite and its cardinality is less than or equal to one plus the number of occurrences of letters from Script A sign appearing in r; (3) any partial derivative of r is either a regular unit, or a subterm of r, or a concatenation of several such subterms. These theoretical results lead us to a new algorithm for turning regular expressions into relatively small NFA's and allow us to provide certain improvements to Brzozowski's algorithm for constructing DFA's. We also report on a prototype implementation of our NFA construction and present several examples.

Original languageEnglish
Pages (from-to)291-319
Number of pages29
JournalTheoretical Computer Science
Volume155
Issue number2
DOIs
Publication statusPublished - 11 Mar 1996
Externally publishedYes

Fingerprint

Dive into the research topics of 'Partial derivatives of regular expressions and finite automaton constructions'. Together they form a unique fingerprint.

Cite this