ゾゾウスキー微分

ウィキペディア

ゾゾウスキー微分

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/11/08 15:06 UTC 版)

Brzozowski derivative (on red background) of a dictionary string set with respect to the string "con"

論理計算機械学、特に 形式言語理論において、 ゾゾウスキー微分 $u^{-1}S$ とは、 文字列 の 集合 $S$ と文字列 $u$ に対して、 $S$ に属する文字列から 接頭辞 $u$ を切り取ることで得られるすべての文字列の集合である。

形式的には、

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

とあらわされる。

例えば、

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

などである。

ゾゾウスキー微分は1950年代後半以降、様々な名称で使用されてきた。 現在では、その性質を研究し、一般化正規表現 の導関数を計算するアルゴリズムを与えた、コンピュータ・サイエンティストのJanusz Brzozowski 氏にちなんで命名されている.

定義

もともとは正規表現のために研究されたものの、この定義は任意の形式言語に適用される。

形式言語 $S$ が、アルファベット $\Sigma$ 上に定義され、任意の文字列 $u\in \Sigma ^{*}$に対して、 $u$ に関する $S$の導関数は次のように定義される。

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

ゾゾウスキー微分は、 $$\ u^{-1}S=\{u\}\;\backslash \;S$$と表せるような、 $u$ のみを含む単項集合による左商の特殊な場合である。

等価的ににすべての $u,v\in \Sigma ^{*}$に対して以下が成立する。

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

定義より、すべての $u,v\in \Sigma ^{*}$に対して以下が成り立つ。

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

なぜならば、すべての $w\in \Sigma ^{*}$に対して、

$w\in (uv)^{-1}S\Leftrightarrow uvw\in S\Leftrightarrow vw\in u^{-1}S\Leftrightarrow w\in v^{-1}(u^{-1}S)$

であるからである。

任意の文字列に対する導関数は、その文字列の記号に対する逐次的な導関数に還元される。なぜなら、すべての $a\in \Sigma ,u\in \Sigma ^{*}$に対して、 $${\begin{aligned}(ua)^{-1}S&=a^{-1}(u^{-1}S)\\\varepsilon ^{-1}S&=S\end{aligned}}$$となるからである。

言語 $S\subseteq \Sigma ^{*}$ は空文字列 $\varepsilon$ を含む限り、nullableであると呼ばれる。各言語 $S$ は、その導関数がnullableであるかによって一意に決定される。 $$w\in S\ \Leftrightarrow \ \varepsilon \in w^{-1}S$$言語は、(潜在的に無限の) ブール値ラベル付き木 (木 (集合論) 及び 無限木オートマトンを参照)とみなすことができる。 可能な各文字列 $w\in \Sigma ^{*}$ は木上のノードを表し、ラベルは $w\in S$ の場合は真、それ以外の場合は偽となる。

この解釈において、記号 $a$ に関する導関数は、根から辺 $a$ を辿って得られる部分技に対応する。木を根と部分技 $a^{-1}S$ に分解することは、以下の等式に対応し、これは任意の言語 $S\subseteq \Sigma ^{*}$に対して成立する。

$$S=(\{\varepsilon \}\cap S)\cup \bigcup _{a\in \Sigma }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 のクリーネ閉包 を表す : L(R*) = L(R)*

一般的な正規表現では、∧も¬も使用することができない。

計算

任意の一般化正規表現 R と任意の文字列 u に対して、導関数 u⁻¹R は再び正規表現 (言語 u⁻¹L(R)を表す)となる。

これは、以下のように再帰的に計算できる。

(ua)−1R	= a−1(u−1R)	記号 a 及び 文字 u に対して
ε−1R	= R

前述の2つの規則を用いることで、任意の文字列に対する導関数は単一記号文字列 a に対する導関数によって説明できる。後者は以下のように計算できる。

a−1a	= ε
a−1b	= ∅	ただし、 b≠a
a−1ε	= ∅
a−1∅	= ∅
a−1(R*)	= (a−1R)R*
a−1(RS)	= (a−1R)S ∨ ν(R)a−1S
a−1(R∧S)	= (a−1R) ∧ (a−1S)
a−1(R∨S)	= (a−1R) ∨ (a−1S)
a−1(¬R)	= ¬(a−1R)

ここで、 ν(R) は 補助関数 であり、R の言語が ε を含む場合に空文字列 ε に評価され、そうでない場合は∅に評価された一般化された正規表現を生成する。この関数は以下の規則によって計算できる。

ν(a)	= ∅	任意の a について
ν(ε)	= ε
ν(∅)	= ∅
ν(R*)	= ε
ν(RS)	= ν(R) ∧ ν(S)
ν(R ∧ S)	= ν(R) ∧ ν(S)
ν(R ∨ S)	= ν(R) ∨ ν(S)
ν(¬R)	= ε	ν(R) = ∅ の場合
ν(¬R)	= ∅	ν(R) = ε の場合

性質

文字列 u が一般化正規表現 R で表される文字列集合の要素であるのは、ε が導関数 u⁻¹R で表される文字列集合の要素である場合に限られる。

固定された一般化正規表現 R のすべての導出形を考慮すると、有限個の異なる言語のみが生じる。それらの数を d_R とすると、これらすべての言語は、長さ d_R 未満の文字列に関して R の導出形として得られる。

さらに、マイヒル＝ネロデの定理 によれば、 R で与えられる正規言語を認識する d_R 個の状態を持つ完全決定有限オートマトン が存在する。

文脈自由言語の導出

導関数は 文脈自由文法と同値な正規表現演算子を用いた再帰的に定義された方程式に対しても効果的に計算可能である。この知見は文脈自由文法の構文解析アルゴリズムの導出に利用された。

このようなアルゴリズムの実装は、一般の文脈自由文法に対するアーリー法の複雑度に相当する時間計算量を持つことが示されている。

関連項目

• Quotient of a formal language