布爾佐夫斯基導數

在理論計算機科學，特別是形式語言理論中，布爾佐夫斯基導數{dISPlaystyleS}的一個字符串和一個字符串的字符串和一個字符串u{diSPlaystyleu}是一個字符串的集合是指可從S中的一個字符串獲得的所有字符串的集合。S{displaystyleS}中的一個字符串獲得的所有字符串的集合。中的一個字符串通過切斷前綴今天，它是以計算機科學家JanuszBrzozowski的名字命名的，他研究了它的特性并給出了計算廣義正則表達式導數的算法。

盡管最初是針對正則表達式研究的，但該定義也適用于任意的形式語言。給定任何形式語言{displaystylewinSigma{*}}，我們就有機會在所有的w∈Σ?中找到它。{displaystylewinSLeftrightarrowvarepsiloninw{-1}S}。一種語言可以被看作是一棵（可能是無限的）布爾標記的樹（也見樹（集合論）和無限樹自動機）。每個可能的字符串{displaystylewinSigma{*}}表示樹中的一個節點。表示樹上的一個節點，標簽為真，當{displaystyleS=({{varepsilon}capS)cupbigcup_{ainSigma}a(a{-1}S).}。

當一種語言由正則表達式給出時，導數的概念導致了一種算法，用于決定某個詞是否屬于正則表達式。給定一個符號的有限字母表A，一個廣義正則表達式R表示字母表A上可能無限長的字符串集，稱為R的語言，表示為L(R)。廣義正則表達式可以是下面的一種（其中a是字母表A的一個符號，R和S是廣義正則表達式）。

?表示空集。L(?)={},ε表示包含空字符串的單子集。L(ε)={ε},a表示包含單符號字符串a的單子集。L(a)={a},R∨S表示R和S的并集：L(R∨S)=L(R)∪L(S),R∧S表示R和S的交集：L(R∧S)=L(R)∩L(S),?R表示R的補集（相對于A*,A上所有字符串的集合）。L(?R)=A*L(R),RS表示R和S的連接：L(RS)=L(R)-L(S),R*表示R的KLeene封閉：L(R*)=L(R)*.在普通正則表達式中，∧和?都是不允許的。

對于任何給定的廣義正則表達式R和任何字符串u，導數u-1R又是一個廣義正則表達式（表示語言u-1L(R)）。