ブロゾフスキー微分

理論計算機科学、特に形式言語理論において、文字列の集合と文字列のブロゾフスキー微分は、文字列から 接頭辞を切り落とすことによって得られるすべての文字列の集合です。正式には、 ${\displaystyle u^{-1}S}$ ${\displaystyle S}$${\displaystyle u}$${\displaystyle S}$ ${\displaystyle u}$

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

例えば、

${\displaystyle c^{-1}\{{\text{猫}},{\text{牛}},{\text{犬}}\}=\{{\text{at}},{\text{ow}}\}.}$

ブロゾフスキー導関数は1950年代後半から様々な名前で導入されてきた。^{[1] [2] [3]}現在では、その特性を調査し、一般化された正規表現の導関数を計算するアルゴリズムを提案したコンピュータ科学者ヤヌシュ・ブロゾフスキー にちなんで名付けられている。^[4]

もともと正規表現のために研究された定義ですが、任意の形式言語にも適用できます。アルファベット上の任意の形式言語 と任意の文字列が与えられた場合、の に関する微分は次のように定義されます。^[5]${\displaystyle S}$${\displaystyle \Sigma }$${\displaystyle u\in \Sigma ^{*}}$${\displaystyle S}$${\displaystyle u}$

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

Brzozowski 微分は、 のみを含む単一集合による左商の特殊なケースです。${\displaystyle u}$${\displaystyle \u^{-1}S=\{u\}\;\backslash \;S}$

同様に、すべての に対して: ${\displaystyle u,v\in \Sigma ^{*}}$

${\displaystyle v\in u^{-1}S\;\Leftrightarrow \;uv\in S.}$

定義より、すべての に対して: ${\displaystyle u,v\in \Sigma ^{*}}$

${\displaystyle (uv)^{-1}S=v^{-1}(u^{-1}S)}$

すべて に対して となるので、 が成り立ちます。${\displaystyle w\in \Sigma ^{*}}$${\displaystyle w\in (uv)^{-1}S\Leftrightarrow uvw\in S\Leftrightarrow vw\in u^{-1}S\Leftrightarrow w\in v^{-1}(u^{-1}S)}$

任意の文字列に関する微分は、その文字列の記号に対する連続した微分に簡約されます。これは、すべての に対して次のようになるためです。 ${\displaystyle a\in \Sigma ,u\in \Sigma ^{*}}$$${\displaystyle {\begin{aligned}(ua)^{-1}S&=a^{-1}(u^{-1}S)\\\varepsilon ^{-1}S&=S\end{aligned}}}$$

言語がnull 可能と呼ばれるのは、空の文字列が含まれている場合のみです。各言語は、その派生語の null 可能性によって一意に決定されます。 ${\displaystyle S\subseteq \Sigma ^{*}}$${\displaystyle \epsilon }$${\displaystyle S}$

${\displaystyle w\in S\ \Leftrightarrow \ \varepsilon \in w^{-1}S}$

言語は、（潜在的に無限の）ブールラベル付きツリーとして見ることができます（ツリー（集合論）および無限ツリーオートマトンも参照）。各可能な文字列はツリー内のノードを表し、ラベルはの場合はtrue、それ以外の場合はfalse です。この解釈では、シンボルに関する導関数は、ルートからエッジをたどることで得られるサブツリーに対応します。ツリーをルートとサブツリーに分解すると、すべての言語で成り立つ次の等式に対応します。 ${\displaystyle w\in \Sigma ^{*}}$${\displaystyle w\in S}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a^{-1}S}$${\displaystyle S\subseteq \Sigma ^{*}}$

${\displaystyle S=(\{\varepsilon \}\cap S)\cup \bigcup _{a\in \Sigma }a(a^{-1}S).}$

言語が正規表現によって与えられる場合、派生語の概念は、与えられた単語が正規表現に属するかどうかを判断するアルゴリズムにつながります。

有限の記号アルファベット Aが与えられた場合、^[6]一般化された正規表現 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のクリーネ閉包を表します：L ( R *) = L ( R )*。

通常の正規表現では、∧ も ¬ も許可されません。

任意の一般化正規表現Rと任意の文字列uに対して、導関数u ⁻ 1Rは再び一般化正規表現（言語u ⁻ 1L（R）を表す）である。^[7] これは次のように再帰的に計算することができる。^[8]

前の2つの規則を用いると、任意の文字列に関する微分は、単一記号文字列aに関する微分によって説明される。後者は次のように計算できる: ^[9]

ここで、ν( R )は、 Rの言語にεが含まれる場合は空文字列εに評価され、そうでない場合は∅に評価される一般化正規表現を生成する補助関数である。この関数は次の規則で計算できる: ^[10]

文字列uが一般化正規表現Rで表される文字列集合のメンバーである場合、かつεが導関数u ⁻ 1Rで表される文字列集合のメンバーである場合に限ります。^[11]

固定された一般化正規表現Rのすべての導関数を考えると、有限個の異なる言語しか得られません。その数をd _Rで表すと、これらすべての言語は、d _R未満の長さの文字列に関するRの導関数として取得できます。^{[12]さらに、}マイヒル-ネローデの定理で述べられているように、Rによって与えられた正規言語を認識するd _R状態を持つ完全な決定性有限オートマトンが存在します。

正規表現演算子を使用して再帰的に定義された方程式の導関数も効果的に計算可能であり、これは文脈自由文法と同等である。この洞察は、文脈自由言語の構文解析アルゴリズムを導出するために使用されました。^{[13]このようなアルゴリズムの実装は3次の}時間計算量 を持つことが示されており、^{[14]一般的な文脈自由文法における}Earleyパーサー の計算量に対応しています。

• 形式言語の商