Brzozowski derivative  In theoretical computer science, in particular in formal language theory, the Brzozowski derivative "u"−1"S" of a set "S" of strings and a string "u" is defined as the set of all strings obtainable from a string in "S" by cutting off a prefixing "u", formally: "u"−1"S" = { "v" ∈ Σ*: "uv" ∈ "S" }, cf. picture. It was introduced under various different names since the late 1950s. Today 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. Even though originally studied for regular expressions, the definition applies to arbitrary formal languages. Given any formal language "S" over an alphabet "Σ" and any string "u" ∈ Σ*, the derivative of "S" with respect to "u" 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 "(uw)"−1"S" = "w"−1("u"−1"S"). 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 (potentially infinite) boolean-labelled tree (see also tree (set theory) and infinite-tree automaton). 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"−1"S" corresponds to the following equality, which holds for every formal language "S"⊆ Σ*:  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.