ブジョゾフスキ微分

サムネイル|245x245ピクセル|Brzozowski derivative (on red background) of a dictionary string set with respect to the string "con" 理論計算機科学、特に 形式言語理論において、 ブジョゾフスキ微分 とは、 文字列 の 集合 と文字列 に対して、 に属する文字列から 接頭辞 を切り取ることで得られるすべての文字列の集合である。

形式的には、

とあらわされる。

例えば、

などである。

ブジョゾフスキ微分は1950年代後半以降、様々な名称で使用されてきた。 現在では、その性質を研究し、一般化正規表現 の導関数を計算するアルゴリズムを与えた、計算機科学者のJanusz Brzozowski 氏にちなんで命名されている。

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

形式言語 が、アルファベット 上に定義され、任意の文字列 に対して、 に関するの導関数は次のように定義される。

ブジョゾフスキ微分は、と表せるような、 のみを含む単項集合による左商の特殊な場合である。

等価的にすべての に対して以下が成立する。

定義より、すべての に対して以下が成り立つ。

なぜならば、すべての に対して、

であるからである。

任意の文字列に対する導関数は、その文字列の記号に対する逐次的な導関数に還元される。なぜなら、すべての に対して、となるからである。

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

この解釈において、記号 に関する導関数は、根から辺 を辿って得られる部分木に対応する。木を根と部分木 に分解することは、以下の等式に対応し、これは任意の言語に対して成立する。

一般化正規表現の導関数 正規表現によって言語が与えられる場合、導関数の概念は、与えられた単語が正規表現に属するかどうかを判定するアルゴリズムにつながる。

有限の記号集合であるアルファベット A が与えられたときBrzozowski (1964), p.481, required A to consist of the 2n combinations of n bits, for some n.、一般化正規表現 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)を表す)となるBrzozowski (1964), p.483, Theorem 4.1。

これは、以下のように再帰的に計算できるBrzozowski (1964), p.483, Theorem 3.2。

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

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

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

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

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

計算例 例として、正規表現 に対する文字 に関する導関数 を計算する。

まず、クリーネ閉包の規則を適用する。

次に、連結の規則と補助関数 を用いて を計算する。 であるため、以下のようになる。

したがって、導関数は最終的に以下のように求められる。

性質 文字列 u が一般化正規表現 R で表される文字列集合の要素であるのは、ε が導関数 u−1R で表される文字列集合の要素である場合に限られるBrzozowski (1964), p.483, Theorem 4.2。

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

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

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

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

関連項目

Quotient of a formal language

参考文献