✖

到達不能状態

有限オートマトンには、どうやってもたどり着けない状態が含まれていることがあります。このような状態を到達不能状態といいます。到達不能状態はオートマトン全体を無駄に複雑にするだけなので、ふつうは取り除きます。

到達不能状態の例

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

何をしても、状態 q3 には決してたどり着けないことがわかります。この状態に向かう遷移が1つもないからです。そこで、状態 q3 は到達不能であるといいます。では、状態 q3 は、ほかの状態からそこへ向かう遷移があれば到達可能になるでしょうか。状態 q0, q1, q2, q5 のどれかから辺を引けば、到達可能になります。しかし、新しいノードを加えて、そこから遷移を引いた場合は…

…当然、状態 q3 と q4 はどちらも到達不能です。

到達不能状態の定義

まず、到達可能な状態を定義します。有限オートマトン A = ⟨Q, Σ, δ, q0, F⟩ を考えます。状態 q ∈ Q が到達可能であるとは、次を満たす語 w ∈ Σ∗ が存在することです。

⟨q0,w⟩↦∗⟨q,ε⟩.

状態 q ∈ Q が到達可能でないとき、その状態は到達不能であるといいます。

到達不能状態の取り除き方

オートマトンに到達不能状態がある場合は、取り除いておくとよいでしょう。そこで、到達不能状態をもたない等価なオートマトン A′ = ⟨Q′, Σ, δ′, q0, F′⟩ をつくります。

到達可能な状態の集合を、手順をくり返しながら組み立てていきます。初期状態は明らかに到達可能なので、集合 S0 = {q0} から始めます。その次の集合は、次のようにつくります。

Si={r|δ(q,a)=r を満たす q∈Si−1,a∈Σ が存在する}∪Si−1

言葉で説明すると、次のようになります。集合 S0 は最初から決まっています。集合 S1 は、集合 S0 のすべての状態について、Σ のすべての記号での遷移がどこへ向かうかを調べてつくります。こうして見つかった状態と、もとの状態の集合 S0 との和集合をとります。同じようにして集合 S2 以降も求めます。明らかに Si − 1 ⊆ Si が成り立ちます。

すると、到達可能な状態の集合は次のように求められます。

⋃i=1∞Si

無限個の集合 Si の和集合をとろうとしているのは、奇妙に見えるかもしれません。しかし、オートマトンの状態は有限個しかありません。そのため、あるところから先は集合 Sj と Sj + 1 以降がすべて等しくなります。無限個の集合の和集合をとっても、得られる状態の集合は有限になるのです。

2つ目のオートマトンにもどります。

このオートマトンについて、到達可能な状態の集合を求めてみましょう。まず、出発点として次の等式をおきます。

S0={q0}

次に、集合 S1 を求めます。状態 q0 から出るすべての遷移を見つけ、その行き先の状態を集合 S0 に加えます。q0 → a q1 と q0 → bq2 が成り立つので、集合 S1 には新たに状態 q1 と q2 が加わります。

S1={q0,q1,q2}

続いて、集合 S2 をつくります。状態 q0, q1, q2 からどこへ行けるかを調べます。新しく加わるのは、状態 q5 だけです。この状態には状態 q1 から行けます。

S2={q0,q1,q2,q5}

さらに、集合 S3 をつくります。状態 q0, q1, q2, q5 から、新しい状態に行けるでしょうか。行けないので、集合 S3 の要素は S2 と同じです。

S3={q0,q1,q2,q5}

S2 = S3 なので、S3 = S4 = S5 = … も成り立ちます。この先どの集合にも新しい要素は加わらないので、すべての Si の和集合をとると集合 S2 が得られます。

よって、このオートマトンの到達可能な状態の集合は {q0, q1, q2, q5} です。到達不能状態は、単純に集合の差をとれば求められます。

Q∖⋃i=1∞Si

このオートマトンの到達不能状態の集合は {q3, q4} です。オートマトン A から、到達不能状態をすべて取り除き、到達不能状態が関わる遷移もすべて取り除きます。つまり、到達不能状態をもたないオートマトン A′ = ⟨Q′, Σ, δ′, q0, F′⟩ で、オートマトン A = ⟨Q, Σ, δ, q0, F⟩ と等価なものを、次のように定義します。

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

参考文献

章: 到達不能状態, 冗長な状態, オートマトンの最小化