布尔佐夫斯基导数

在理论计算机科学，特别是形式语言理论中，布尔佐夫斯基导数{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)）。