オートマトンから正規表現への変換

任意の有限オートマトンを正規表現に変換する方法を説明します。

アルゴリズムの概要

入力として NFA A が与えられているとします。まず、これを GNFA に変換します。次の段階では、1ステップごとに状態を1つ除去し、そのたびに遷移関数を正しく修正します。これを、初期状態と受理状態の2つの状態だけが残るまでくり返します。その2つの状態の間には辺が1本あり、その辺につけられた正規表現がアルゴリズム全体の結果になります。つまり、この方法の中心は、状態を1つ除去したあと、等価なオートマトンになるようにオートマトンを修正することです。

状態を1つ除去する方法

状態を1つ除去する方法を、簡単な例で見てみましょう。オートマトンの一部が次のようになっているとします。

ここで、R_i はある正規表現です。状態 q_r を除去すると、オートマトンはどうなるでしょうか。状態 q_i にいるとして、この部分でどんな語をつくれるかを考えてみます。状態 q_i から状態 q_j へ直接進む場合は、正規表現 R₄ に当てはまるすべての語がつくれます。

一方、状態 q_r へ進む場合は、R₁ の形の語がつくれます。さらに、状態 q_r では正規表現 R₂ についてループできるので、実際には $R_1\circ (R_2^{\ast })$ の形の語がつくれます。そして、状態 q_r から状態 q_j へも進めるので、そこに正規表現 R₃ を加えます。全体として、この経路では $R_1\circ (R_2^{\ast })\circ R_3$ の形の語が得られます。

これで、オートマトンのこの部分からは、R₄ の形の語か、$R_1\circ (R_2^{\ast })\circ R_3$ の形の語ができることがわかりました。これはもちろん、正規表現で $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$ と書けます。

ここまでくれば、状態 q_r を除去して q_i と q_j の2つの状態だけを残し、R₄ の代わりに、いま求めた正規表現を書くだけです。

この手順を、各状態 q_i から状態 q_j へのすべての辺について行います。自己ループ、つまり q_i = q_j の場合も含みます。

状態を1つ除去すると、等価なオートマトン、つまり同じ言語を受理するオートマトンが得られます。

アルゴリズム全体

入力として NFA A = ⟨Q, Σ, δ, q₀, F⟩ が与えられているとします。

1. NFA A を GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩ に変換します。以下、Z の状態の個数を文字 k で表します。
2. k = 2 ならアルゴリズムは終了し、初期状態と受理状態の間の辺についている正規表現が求める結果です。
3. k>2 なら、初期状態とも受理状態とも異なる任意の状態 q_r、つまり q_r ≠ q₀′ かつ q_r ≠ q_f′ を満たす状態を選びます。そして、次の条件を満たす新しい GNFA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ をつくります。 $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ また、すべての q_i ∈ Q′′ ∖ {q_f′} とすべての q_j ∈ Q′′ ∖ {q₀′} について、次のように定めます。 $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3)$$ ここで、R₁ = δ′(q_i,q_r)、R₂ = δ′(q_r,q_r)、R₃ = δ′(q_r, q_j)、R₄ = δ′(q_i, q_j) です。 そのあと、手順2にもどります。

例

入力として、次の有限オートマトンが与えられているとします。

まず、これを GNFA に変換します（不要な ∅ の遷移はかきません）。

次に、アルゴリズムの後半を適用して、ノードを1つ除去します。ノード q₂ から始めましょう。ノード q₂ を除去し、状態 q₁ から状態 q_f への遷移を加えます。この遷移には b(a|b)^∗ をつけます。ノード q₁ からは b の形の語で状態 q₂ に移り、そこで a|b についてループできるので (a|b)^∗ が得られ、最後に ε 遷移で q_f に移るからです。このとき、b(a|b)^∗ϵ = b(a|b)^∗ が成り立ちます。次のオートマトンが得られます。

残りは最後の状態 q₁ の除去です。状態 q_s から状態 q_f への辺を加えます。この辺には何をつければよいでしょうか。状態 q₁ へは ε 遷移で移るので、これはそのまま省けます。次に、a についてループできるので、正規表現 a^∗ が得られます。最後に辺を通って q_f に移るので、この式に b(a|b)^∗ を連接します。したがって、この辺には正規表現 a^∗ b(a|b)^∗ をつけます。

オートマトンの状態は2つだけになったので、アルゴリズムは終了します。辺についているのが、求める正規表現です。

参考文献

• 例とアルゴリズムの説明は M. Sipser: Introduction to the Theory of Computation によります。