Rahul Sharma (Editor)

Brzozowski derivative

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In theoretical computer science, in particular in formal language theory, the Brzozowski derivative u−1S of a set S of strings and a string u is defined as the set of all rest-strings obtainable from a string in S by cutting off its prefix u (if possible), formally: u−1S = { v ∈ Σ*: uv ∈ S }, cf. picture. It is named after the computer scientist Janusz Brzozowski who investigated their properties and gave an algorithm to compute the derivative of a generalized regular expression.

Contents

Derivative of a 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:

  • ∅ (denoting the empty set of strings),
  • ε (denoting the singleton set containing just the empty string),
  • a symbol a from A (denoting the singleton set containing the single-symbol string a),
  • R∨S (where R and S are, in turn, generalized regular expressions; denoting their set's union),
  • R∧S (denoting the intersection of R 's and S 's set),
  • ¬R (denoting the complement of R 's set with respect to the set of all strings of symbols from A),
  • RS (denoting the set of all possible concatenations of strings from R 's and S 's set),
  • R* (denoting the set of n-fold repetitions of strings from R 's set, for any n≥0, including the empty string).

    • 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(R).

    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, ν(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:

    Properties

    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.

    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.

    References

    Brzozowski derivative Wikipedia
    (Text) CC BY-SA