到達可能状態の検出

到達不可能状態はFAの動作に関与しないため、与えられたFAから到達不可能な状態とそれか ら遷移を取り除いて得られるFA^は元のFA^{とは等価である。}

初期状態q0を到達可能状態検出木の根の名前とし、各入力記号によって根から遷移する状態を 付け加え、既出の名前を持つ頂点からは伸ばさないようにして到達可能状態検出木を構成する。有 限状態機械であるため、この検出木の構成は有限個の頂点を有する木として完了する。

到達不可能状態は、FA^{の状態集合}Qから到達可能状態を逐次的に取り出した集合R(Q)^を決定 し、残余Q\R(Q)の状態として検出できる。このことを保証するの次の命題が成立する。

命題5.1 ^初期状態q0から任意の入力x∈Σ^に対しq0

⇒x^∗

M p^{によって一意的に状態}p^{へ到達可能で} あるDFAM^{について、}Mの到達可能状態はすべて検出できる。この命題は以下の主張と同等で

|x|≦n^{である任意の入力}x∈Σ^{に対して、}p0

⇒x^∗

M p^{である状態}pは到達可能状態検出木内に名前 pを持つ頂点として存在している。

証明 数 nに関する帰納法によって、命題が成立することを証明する。n = 0^{の場合、状態} p=q0は到達可能木の根として存在している。

n=k≧0のときに成立していると仮定してk+1^{での成立を示す。}|x|=k^なるx∈Σ^によって 遷移した状態をpとしたとき、帰納法の仮定から、名前pを持つ頂点は到達可能状態検出木の頂点 として登場している。長さがk+1^の入力列y=xa∈Σ^に対してδ(p,a)=p^{′とすると、名前}p^′を 持つ頂点は名前pを持つ検出木の子頂点として検出木に登場していなければならない。したがっ て、長さk+1の任意の入力列についての命題が成立していることが示された。

例5.1 ^図5.1^左の機械M^{において、状態}s^{には初期状態}q0からはいかなる入力によっても到達す ることができない。このためにM^から状態s^{を除去しても}Mが受理する言語が変わることはな い。図5.1^右の機械M^′は、M^{から到達不可能状態}sを取り去って得られる等価な機械である。

M

q0

start

r s

t

0

0

0 1

0

1 0

1

≡ M^′

q0

start

r

t 0

0

0 1

0 1

図5.1 M^{の到達不可能状態}sを見いだし除去して得られる同じ言語を受理するM^′

実際に機械M^{の到達不可能状態が}sであることを検出するための到達可能状態検出木は図5.2 のように構成できる。初期状態q0を検出木の根として⓪番目に決定し、入力0^{によって遷移する} 状態q0を①番目、入力1^{によって遷移する状態}rを②番目として決定する。これを続けて、②番 目の状態r^から1^{で遷移する④番目の}rは既に②で登場しているため、④番目から検出木の枝は伸 びない。また、③番目の状態t^から0^{で遷移する⑤番目の}t^と,1^{で遷移する⑥番目の}r^{も検出木に} 既出であるので、これ以上の枝を伸ばすことができずに到達可能状態検出木が完成する。この検出 木の頂点から定まる集合が到達可能状態R(Q)={q0,r,t}となる。到達不可能状態はQ={q0,r,s,t}

から到達可能状態を差し引いたQ\R(Q)={s}として求めることができる。

⓪q0

①q0 ②r

③t ^④r

⑤t ^⑥r 0

1

0 1

0 1

図5.2 ^図5.1^の機械Mの到達可能状態検出木。初期状態q0を0番目の根として、 入力0,1^に よって遷移する状態を下方に伸ばして到達可能状態検出木を構成。0^番目から6^{番目以降では} 新たな状態遷移パターンp⇒^x

M qとなる頂点は存在せず、到達可能状態検出木が完成して、この 検出木の頂点からなる集合として到達可能状態R(Q)={q0,r,t}^{が定まる。}

5.3 2 ^{つの機械の等価性判定}

2^つのDFAM1とM2が等価であることを判定するアルゴリズムを考えよう。定義5.1^から、同 じ入力アルファベットΣ^を持つ2^つのDFAM1=(Q1,Σ, δ1,q01,F1)^とM2=(Q2,Σ, δ2,q02,F2)^が 等価M1≡M2で同じ言語を受理するL(M1)=L(M2)であるためには、任意の入力列x∈Σ^{∗ に対} して

q01⇒x M1

p1 かつ q02 ⇒x M2

p2

である状態p1 ∈Q1とp2 ∈Q2が、共に受理状態p1 ∈F1,p2∈ F2であるか、または共に非受理状 態p1 <F1,p2 <F2であらねばならない。もし遷移先の状態p1,p2で片方が受理状態で他方が非受 理状態となるような入力列x^{が存在すれば、}L(M1),L(M2)^{となってしまう。}M1 ≡M2であると き、定義5.2より共通の入力列による遷移先の状態p1とp2は等価p1≡p2である。

機械M₁ ^とM₂の等価性判定は、共通の入力列によって到達する状態対について片方が受理状 態、もう一方が非受理状態であるような状況が生じないことを確認すればよい。

このために、例5.1で到達可能状態検出木を構成したように、以下のようにして等価性判定木 (comparision tree)を構成する。確認すべき状態対は高々|Q1| × |Q2|個と有限であることから、こ の手続きは常に完了する。

まず初期状態q01 とq02 とは等価q01 ≡q02 として等価性判定木の根の名前とする。各入力記号 によって根の2^状態q01およびq02 から遷移する2状態が等価であることを調べて≡^{記号で書く。}

この手続きを続けて新たに遷移した2状態が等価であることを調べながら等価性判定木を伸ばして

ばさないようにすると、それ以上新たな2状態の等価式が生じないような木として等価性判定木が 完成する。

例5.2 ^図5.3^{で与えられる機械}M1とM2の等価性を判定してみよう。

M1

q0

start

q2

q1 q3

0

0 0

0

1 1

1

1

≡ M2

r0

start

r1

0

1

0 1

図5.3 M1とM2は入力記号0,1からなる同じ言語を受理する同等な機械

まず、状態qiに到達する言語の正規表現R_i に関する連立線形再帰式を考えて、M1とM2で受 理される言語の正規表現を求めておこう。M1については

R₀=ε

R₁=R₀1+R₁0+R₂1+R₃1 R₂=R₀0+R₂0

R₃=R₁1+R₃0.

R₀ =ε^{を使って、}R₂について解くことができてR₂ =00^{∗、これより}R₃ =R₁10^{∗ を得る。よっ} て、R₁ = 1+R₁0+00^∗1+R₁10^∗1. ^{これを解いて、}R₁ = (1+00^∗1)(0+10^∗1)^{∗ を得る。した} がって、R₃ = (1+00^∗1)(0+10^∗1)^∗10^∗. ^これよりM1 が受理する言語の正規表現はR₁+R₃ = (1+00^∗1)(0+10^∗1)^∗(ε+10^∗)^{で与えられる。}

M₂^{については} R₀=ε+R₀0

R₁=R₀1+R₁(0+1).

これを解いて、M2が受理する言語の正規表現は0^∗1(0+1)^{∗ となる。}

正規表現に関する関係式、特にKleeneの閉包演算の性質（演習4.1^{）に注目すると、この}2^つ の機械が受理する言語の正規表現が一致することを示すことができるが、見通しが芳しくない。こ れについては、節5.7の有限オートマトンの最小化で、統一的な方法を考えることにする。

さて、図5.4にあるように、⓪番目の等価式q0≡r0から入力によって遷移した状態の等価性（共 に受理状態であるか、または共に非受理状態になっている）を調べてみると①番目、②番目の等価 式を得る。この操作は、以降③番目から⑧番目まで続けられるが、③、④番目や⑦,^{⑧番目からは}

新たな等価式を生じないことが確認でき、等価性判定木は⓪番目から⑧番目の頂点を持つ木として 構成できる。その結果、機械M1とM2の等価性が示される。

⓪q0≡r0

①q2≡r0 ②q1≡r1

③q2≡r0 ④q1≡r1 ⑤q1≡r1 ⑥q3≡r1

⑦q3≡r1 ⑧q1≡r1

0

1

0 1

0 1

0 1

図5.4 ^{等価性判定木。図}5.3^の機械M1の初期状態q0とM2の初期状態r0を0^{番目の等価性} q0≡r0として根とし、入力から遷移する等価式を以降同様にして1^番目から8^{番目として得ら} れる木からは新たな等価式は生じず、等価性判定木が得られる。

例5.3 M2（図5.3^{右）は、次の}M3（図5.5^{右）とは等価ではない}M2.M3ことを示すことがで きる。

M2

r0

start

r1

0

1

0 1

.

M3

s0

start

s1

0 1

0 1

図5.5 M2とM3は入力記号0,1からなる異なる言語を受理する機械

図5.6 ^{のように、機械} M2 の初期状態r0 とM3 の初期状態s0 を0 ^{番目の等価式} r0 ≡ s0 を 根として、入力に応じた遷移状態を考える。δ2(r0,0) = r0 < F1 と非受理状態に遷移する一方、

δ3(s0,0)s1 ∈F3と受理状態に遷移することがわかり、r0.s1である。したがって、M2.M3であ ることが判定できる。

⓪r0≡s0

①r0.s1 ②r₁≡s₁ 0

1

図5.6 ^{非等価性の判定木。図}5.5^の機械M2の初期状態r0とM3の初期状態s0を0^番目の等 価式r0≡s0を根とし、0,1入力からの遷移状態についての等価性を調べてみる。1^{番目の頂点の} 等価性はr0.s1であることから、M2.M3であることが判定できる。

実際、M2が受理する言語の正規表現R₂^は0^∗1(0+1)^{∗である。一方、}M3の各状態で遷移する 言語の正規表現は、節4.4の線形再帰方程式の方法に従って

S₀=ε, S₁=S₀(0+1)+S₁(0+1)

の関係にあることから、M3が受理する言語の正規表現は(0+1)(0+1)^∗ =0(0+1)^∗+1(0+1)^∗と なる。したがって、0^∗1(0+1)^∗ ,(0+1)(0+1)^{∗、つまり}M2 .M3である。たとえば、1^個以上 の0^{からなる言語}0^†はM2では受理されないが（1^{が入力されて受理状態}r1に遷移する必要があ る）、M3では受理される（1^つ以上の0^または1が入力されれば受理状態s1に遷移する）。

演習5.3 ^図5.1^の機械M^とM^′ が等価であることを等価性判定木を構成することによって確かめ なさい。