Brzozowski derivative
In theoretical computer science, in particular in formal language theory, the Brzozowski derivative
by cutting off the prefix
Formally: For example, The Brzozowski derivative was introduced under various different names since the late 1950s.
[1][2][3] Today it is named after the computer scientist Janusz Brzozowski who investigated its properties and gave an algorithm to compute the derivative of a generalized regular expression.
[4] Even though originally studied for regular expressions, the definition applies to arbitrary formal languages.
is defined as:[5] The Brzozowski derivative is a special case of left quotient by a singleton set containing only
The derivative with respect to an arbitrary string reduces to successive derivatives over the symbols of that string, since for all
is called nullable if and only if it contains the empty string
is uniquely determined by nullability of its derivatives: A language can be viewed as a (potentially infinite) boolean-labelled tree (see also tree (set theory) and infinite-tree automaton).
Each possible string
denotes a node in the tree, with label true when
In this interpretation, the derivative with respect to a symbol
corresponds to the subtree obtained by following the edge
Decomposing a tree into the root and the subtrees
corresponds to the following equality, which holds for every language
: 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,[6] a generalized regular expression R denotes a possibly infinite set of finite-length strings over the alphabet A, called the language of R, denoted L(R).
A generalized regular expression can be one of the following (where a is a symbol of the alphabet A, and R and S are generalized regular expressions): In an ordinary regular expression, neither ∧ nor ¬ is allowed.
For any given generalized regular expression R and any string u, the derivative u−1R is again a generalized regular expression (denoting the language u−1L(R)).
[8] 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:[9] Here, ν(R) 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:[10] A string u is a member of the string set denoted by a generalized regular expression R if and only if ε is a member of the string set denoted by the derivative u−1R.
[11] 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 strings of length less than dR.[12] Furthermore, there is a complete deterministic finite automaton with dR states that recognises the regular language given by R, as stated 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.
[13] Implementation of such algorithms have shown to have cubic time complexity,[14] corresponding to the complexity of the Earley parser on general context-free grammars.
