クリーネのアルゴリズム

理論計算機科学、特に形式言語理論において、クリーネのアルゴリズムは、与えられた非決定性有限オートマトン(NFA)を正規表現に変換する。他の変換アルゴリズムとともに、正規言語のいくつかの記述形式の同等性を確立する。同じ方法の別の表現としては、ブロゾフスキーとマクラスキーによる「消去法」 、マクノートンと山田のアルゴリズム、^{[1]、および}アーデンの補題の使用などがある。

GrossとYellen (2004)によると、^{[2]アルゴリズムは}Kleene (1956)にまで遡ることができます。 ^[3]決定性有限オートマトン(DFA)の場合のアルゴリズムのプレゼンテーションは、HopcroftとUllman (1979)で提供されています。^[4]以下のNFAのアルゴリズムのプレゼンテーションは、GrossとYellen (2004)に従っています。^[2]

非決定性有限オートマトン M = ( Q , Σ, δ, q ₀ , F )、Q = { q ₀ ,..., q _n }の状態集合が与えられた場合、アルゴリズムは次を計算する。

集合R^キイジ
_​kより大きい番号の状態を経由せずにM を状態q _iからq _jに移行させるすべての文字列。

ここで、「状態を通過する」とは、その状態に入ることとそこから出ることを意味するため、 iとj は両方ともkよりも高くなる可能性がありますが、中間の状態はそうではありません。各セットR^キイジ
_​は正規表現で表現され、アルゴリズムはk = -1, 0, ..., nについて段階的に計算する。nより大きい番号の状態は存在しないので、正規表現R^n0j
_さんは、 Mを開始状態 q ₀からq _jまで取るすべての文字列の集合を表す。F = { q ₁ ,..., q _f }が受け入れ状態の集合である場合、正規表現R ₀₁ ^{1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 56 67 78 89 90 100 110 1}
| ... |り_0f^の
Mが受け入れる言語を表します。

k = -1の場合の初期正規表現は、i ≠ jに対して次のように計算されます。

R⁻¹
_ij= a ₁ | ... | a _m       ただしq _j ∈ δ( q _i , a ₁ )、...、q _j ∈ δ( q _i , a _m )

i = jの場合、次のようになります。

R⁻¹
_ii= a ₁ | ... | a _m | ε ただしq _i ∈ δ( q _i , a ₁ ), ..., q _i ∈ δ( q _i , a _m )

つまり、R⁻¹
_ijiからjへの遷移を表すすべての文字を記述し、 i = jの場合には ε も含めます。

その後、各ステップで式R^キイジ
_​前のものから計算すると

R^キイジ
_​=り^{k -1}
_ik（R^{k -1}
_kk) ^* R^{k -1}
_kj|り^{k -1}
_ij

アルゴリズムの動作を理解する別の方法は、「消去法」として理解することです。これは、0からnまでの状態が順次削除される方法です。状態kが削除されると、正規表現R^{k -1}
_ijは、状態i > kから状態j > kへの経路をラベル付けする単語を記述し、 Rに書き換えられる。^キイジ
_​「除去された」状態kを経由する可能性を考慮するためです。

kに関する帰納法によって、各式Rの長さ^[5]が示される。^キイジ
_​最大で⁠1/3⁠ (4 ^{k +1} (6 s +7) - 4) 個のシンボル、ここでs はΣ 内の文字数を表します。したがって、Mが受け入れる言語を表す正規表現の長さは最大で⁠1/3⁠ (4 ^{n +1} (6 s +7) f - f - 3) シンボル、ここでf は最終状態の数を表します。この指数関数的な爆発は避けられません。なぜなら、同等の正規表現が指数関数的なサイズになる必要がある DFA のファミリーが存在するからです。^[6]

実際には、アルゴリズムを実行して得られる正規表現のサイズは、手順によって状態が考慮される順序、つまり 0 からnまでの番号が付けられる順序によって大きく異なる可能性があります。

図に示すオートマトンMは、 M = ( Q , Σ, δ, q ₀ , F ) と記述でき、

• 状態の集合Q = { q ₀ , q ₁ , q ₂ }、
• 入力アルファベットΣ = { a , b }、
• 遷移関数 δ は、 δ( q ₀ , a )= q ₀、 δ( q ₀ , b )= q ₁、 δ( q ₁ , a )= q ₂、 δ( q ₁ , b )= q ₁、 δ( q ₂ , a )= q ₁、 δ( q ₂ , b )= q ₁、
• 開始状態q ₀、および
• 受け入れ状態の集合F = { q ₁ }。

クリーネのアルゴリズムは、最初の正規表現を次のように計算する。

その後、R^キイジ
_​Rから計算される^{k -1}
_ijk = 0、1、2 について段階的に説明します。クリーネ代数等式を使用して、正規表現を可能な限り簡略化します。

ステップ0

ステップ1

ステップ2

q _{0 は}開始状態であり、q _{1 は}唯一の受け入れ状態であるため、正規表現R²
₀₁オートマトンが受け入れるすべての文字列の集合を表します。

• フロイド・ワーシャルアルゴリズム— 特定のクリーネ代数を用いたクリーネアルゴリズムによって実装できる重み付きグラフ上のアルゴリズム
• スターの高さの問題— 特定の DFA に対応するすべての正規表現のスターの最小のネスト深度はどれくらいでしょうか?
• 一般化されたスターの高さの問題- 正規表現で補数演算子が追加で許可されている場合、 Kleene アルゴリズムの出力のスターのネストの深さを固定された境界に制限できますか?
• トンプソンの構築アルゴリズム- 正規表現を有限オートマトンに変換する