Even though originally studied for regular expressions, the definition applies to arbitrary formal languages. Given any formal languageS over an alphabetΣ and any string u ∈ Σ*, the derivative of Swith respect tou is defined as: An equivalent way of stating this is, for all u,v ∈ Σ*: which provides some intuition for the notation. From the definition, for all u,v,w ∈ Σ*: so −1S = w−1. The derivative with respect to an arbitrary string reduces to successive derivatives over the symbols of that string because, for a∈ Σ, u∈ Σ*: A language L⊆ Σ* is called nullable if it contains the empty string, that is, ε ∈ L. Each language S is uniquely determined by nullability of its derivatives: A language can be viewed as a boolean-labelled tree. Each possible string w ∈ Σ* denotes a position in the tree, with binary label true when w ∈ S and false when w ∉ S. In this interpretation, the derivative with respect to a symbol a corresponds to computing the subtree obtained by following the edge a. Decomposing tree into the root and the subtrees a−1S corresponds to the following equality, which holds for every formal language S⊆ Σ*:
Derivatives of generalized regular expressions
When a language is given by a regular expression, the concept of derivatives leads to an algorithm for deciding whether a given word belongs to the regular expression. Given a finite alphabet A of symbols, a generalized regular expression denotes a possibly infinite set of finite-length strings of symbols from A. It may be built of:
∅,
ε,
a symbol a from A,
R∨S,
R∧S,
¬R,
RS,
R*.
In an ordinary regular expression, neither ∧ nor ¬ is allowed. The string set denoted by a generalized regular expression R is called its language, denoted as L.
Computation
For any given generalized regular expression R and any string u, the derivative u−1R is again a generalized regular expression. It may be computed recursively as follows. Using the previous two rules, the derivative with respect to an arbitrary string is explained by the derivative with respect to a single-symbol string a. The latter can be computed as follows: Here, ν is an auxiliary function yielding a generalized regular expression that evaluates to the empty string ε if R 's language contains ε, and otherwise evaluates to ∅. This function can be computed by the following rules:
Properties
A string u is a member of the string set denoted by a generalized regular expression Rif and only if ε is a member of the string set denoted by the derivative u−1R. Considering all the derivatives of a fixed generalized regular expression R results in only finitely many different languages. If their number is denoted by dR, all these languages can be obtained as derivatives of R with respect to string of length below dR. Furthermore, there is a complete deterministic finite automaton with dR states which recognises the regular language given by R, as laid out by the Myhill–Nerode theorem.
Derivatives are also effectively computable for recursively defined equations with regular expression operators, which are equivalent to context-free grammars. This insight was used to derive parsing algorithms for context-free languages. Implementation of such algorithms have shown to have cubic complexity, corresponding to the complexity of Earley parser on general context-free grammars.
