Brzozowski derivative

In theoretical computer science, in particular in formal language theory, the Brzozowski derivative ${\displaystyle u^{-1}S}$ of a set ${\displaystyle S}$ of strings and a string ${\displaystyle u}$ is the set of all strings obtainable from a string in ${\displaystyle S}$ by cutting off the prefix ${\displaystyle u}$. Formally:

${\displaystyle u^{-1}S=\{v\in \Sigma ^{*}\mid uv\in S\}}$.

For example,

${\displaystyle c^{-1}\{{\text{cat}},{\text{cow}},{\text{dog}}\}=\{{\text{at}},{\text{ow}}\}.}$

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]