冗長な状態

有限オートマトンには、そこから受理状態にたどり着けず、役に立たない状態が含まれていることがあります。このような状態を冗長な状態といいます。冗長な状態はオートマトン全体を無駄に複雑にするだけなので、ふつうは取り除きます。

冗長な状態の例

次の有限オートマトンを考えます。

状態 q₄ または q₅ に入ってしまうと、受理状態 q₁、q₂ のどちらにも二度とたどり着けないことがわかります。このような状態は冗長なので、そのまま取り除くことができます。取り除いて得られる新しいオートマトンは、もとのオートマトンと等価です。つまり、同じ言語を受理します。冗長な状態を削除すると、オートマトンは次のようになります。

このオートマトンも同じ言語を受理します。ただし、冗長な状態があったほうがよい場合もあります。例えば、完全なオートマトンをつくるときです。

冗長な状態の定義

有限オートマトン A = ⟨Q, Σ, δ, q₀, F⟩ を考えます。状態 q ∈ Q が冗長であるとは、次を満たす語 w ∈ Σ^∗ と受理状態 q_f ∈ F が1つも存在しないことです。

$$⟨q,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩.$$

冗長な状態の取り除き方

入力として、到達不能状態をもたないオートマトン A = ⟨Q, Σ, δ, q₀, F⟩ が与えられているとします。まず受理状態に向かう状態を見つけ、次に「受理状態に向かう状態」に向かう状態を見つけ、というようにくり返していきます。こうして、冗長でないすべての状態の集合が得られます。最初に S₀ = F とおきます。続いて、集合 S_i を i ∈ ℕ について次の規則でつくります。

$$S_i=\{q\in Q|\mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

こうして得られる、冗長でない状態全体の集合は、次のように表せます。

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

また、冗長な状態の集合は次のとおりです。

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

言いかえると、S_i = S_{i + 1} が成り立てば、集合 Q ∖ S_i の要素が冗長な状態です。この手順を、次のオートマトンで説明します。

まず、S₀ = {q₁, q₂} とおきます。次に、集合 S₁ をつくります。集合 S₀ に、S₀ のどれかの状態に向かうすべての状態を加えます。加わるのは、状態 q₀ と q₃ です。q₀ から q₁ への遷移があり、q₃ から q₂ への遷移があるからです。S₁ = {q₀, q₁, q₂, q₃} が得られます。S₀ ≠ S₁ なので、さらに続けます。

集合 S₂ をつくります。S₁ に行くことができて、まだ S₁ に入っていない状態をすべて探します。そのような状態はただ1つ、q₆ で、ここから状態 q₃ に行けます。S₂ = {q₀, q₁, q₂, q₃, q₆} が得られます。S₁ ≠ S₂ なので、さらに続けます。

集合 S₃ をつくります。S₂ のどれかの状態に行ける新しい状態はあるでしょうか。ありません。状態 q₄ と q₅ からは S₂ のどの状態にも行けず、ほかの状態はすでに S₂ に入っています。よって、S₃ = {q₀, q₁, q₂, q₃, q₆} です。S₂ = S₃ なので、アルゴリズムは終了し、集合 S₂ が冗長でない状態の集合になります。集合 {q₄, q₅} が冗長な状態の集合です。

形式的には、冗長な状態をもたない新しい等価なオートマトンを次のようにつくります。オートマトン A = ⟨Q, Σ, δ, q₀, F⟩ が与えられたとき、これと等価で冗長な状態をもたないオートマトン A′ = ⟨Q′, Σ, δ′, q₀, F⟩ を次のように定めます。

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)（ただし δ(q, a) ∈ Q′ の場合。そうでない場合、δ′(q, a) は定義されません）

参考文献

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools