Derivatives

Regular expressions are the natural formalism arising from an attempt to devise solutions to the symbolic equations encountered in trying to trace out all the possible paths through a network. They comprise one of three productive viewpoints; the other two being, first, the diagrammatic or graphical representation of the network, and second, a relatively numerical description of the network via its connectivity matrix.

The symbolic equations defining regular expressions are soon seen to be the simplest examples of a whole hierarchy of symbolic equations, both implicit and explicit, with various restrictions on the precise form which the system is permitted to assume. Just because they lie at the bottom of the hierarchy, it is worthwhile to make an exhaustive study of their properties, which will surely be encountered again and again in any more comprehensive theory.

Having obtained regular expressions as the description of the paths through a diagram, the converse question arises as to whether there is a diagram for an arbitrarily given regular expression. If such there were, it would be a diagram relating how one regular expression differed from another by its initial letter, in the case the regular expression were solving exit equations, or by its terminal letter, in the case of solutions to entrance equations. Since the two cases are symmetric, it suffices to study one of them---which might as well the case of prefixes.

One of the charming aspects of this theory is its formal resemblance to the differential calculus of analysis. J. Brzozowski developed this point of view, explicitly incorporating the notation of partial derivatives, in an article[17] published in the Journal of the Association for Computing Machinery in 1961. The basic concept is the following: Let be a set of letters, be the set of all finite sequences of letters from , and be some other subset of . Perhaps it could be the set of words represented by a given regular expression, but this is not necessary for the definition.

The derivative of with respect to a is defined to be the set

In other words, it is the set of tails of the words in which begin with the letter a.

Sets are the derivatives of sets; since regular expressions define sets it remains only to verify that their derivatives are also described by regular expressions, to be able to talk directly about the derivatives of regular expressions. The easiest way to attack the problem is to resort to the axiomatic definition of regular expressions, thereby obtaining a list of rules defining the derivatives of composites in terms of the derivatives of their constituents. It is at this point that the formal resemblance to differential calculus becomes apparent, evidently being thereby responsible for the terminology.

A functional notation is convenient; for example might be a regular (or other) expression built up explicitly from variables , all belonging to , using specific operations or further functions similarly defined. At one point it is required to know whether the null word could be represented by f; the easiest way to find out is to evaluate f with zero (empty set, not null word; they're different) arguments. Let us designate this particular value of f by :

Then, given as above, null, and zero, we have:

• definition of a regular expression
  1. is a regular expression
  2. is a regular expression
  3. is a regular expression
  4. if x and y are regular expressions, so is xy
  5. if x and y are regular expressions, so is x + y
  6. if x is a regular expression, so is

• regular expression whose arguments are zero
  1. 
  2. 
  3. 
  4. 
  5. 
  6. 

• derivative of a regular expression
  1. 
  2. 
  3. 
  4. 
  5. 
  6. 
  7. 

  Note that is required in the ``product'' rule because we must devote our attention to the second ``factor'' if the first is the null word; otherwise the first ``factor'' is long enough to yield a derivative without regard to what follows it.

• canonical form

  

The evident way to get a diagram corresponding to a regular expression f is to start with a node labelled f, and to connect it to a node labelled via an outgoing link labelled a, to a node labelled via an outgoing link labelled b, and so on. The canonical form guarantees that we have the correct set of exit equations; the term determines whether we have a terminal node or not.

To incorporate additional nodes into the diagram, it is necessary to take further derivatives, which can be done recursively by applying the definitions once again. Our only real doubt is whether or not there is a finite total number of derivatives, so that the diagram will be finite. Higher derivatives correspond to words which begin with a specified sequence of letters rather than just a single letter; sometimes this is written as a single derivative with respect to the longer sequence.