## 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 language | English |
---|---|

Pages (from-to) | 291-319 |

Number of pages | 29 |

Journal | Theoretical Computer Science |

Volume | 155 |

Issue number | 2 |

DOIs | |

Publication status | Published - 11 Mar 1996 |

Externally published | Yes |