状態対の等価性判定

⓪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^′ が等価であることを等価性判定木を構成することによって確かめ なさい。

M1 q0

start

q2

q1 q3

0

1 1

0

0 0

1

1

.

M4 q0

start

q2

q1 q3

0

1 1 0

0 0

1

1

図5.7 等価な状態を有する機械M1とM4

M1とM4において、非受理状態の集合{q0,q2}^{と受理状態の集合}{q1,q3}^{に属する状態対は明ら} かに等価ではないことから、いずれの機械においても状態対q0,q2とq1,q3の等価性を調べれば よい。

演習5.4 ^機械M4が受理する言語の正規表現を求めて、M1が受理する言語の正規表現と比較して みなさい。

図5.8^はM1の2つの状態対を根としてその等価性判定木を構成した様子である。q0,q2とq1,q3

の遷移から得られる等価性判定木の頂点に全て真なる等価性式が得られることから、2^{つの状態対} は等価であることが判定できる。これによって、2^{つの状態対を}1つにまとめても機械が受理する 入力文字列は変わらないことがわかる。こうして同じ言語を受理する簡単化された機械M^′₁ ^が図 5.9^で、例5.2^においてM1と等価だと示したM2（図5.3）と同型である（状態名称について1^対 1^{の対応がある）。節}4.3の正規表現の表記では、M^′₁^{したがって}M1は正規言語0^∗(0+1)^{∗ を受理} する。

⓪q0 ≡q2

①q2≡q2 ②q1≡q1

0

1

⓪q1≡q3

①q1≡q3 ②q3 ≡q1

0

1

図5.8 ^機械M1の状態対の等価性。状態q0とq2およびq1とq3は共に等価であり、機械M1

は2^{つの等価な状態対を}1つにまとめて同じ言語を受理する機械M^′₁を構成することができる。

M^′₁ q0

start

q1

1 0

0 1

図5.9 M1の2^組の状態q0とq2およびq1とq3をまとめて得られる等価な簡略化機械M^′₁^（図 5.3^のM2と同型）

図5.10^はM4の2つの状態対を根としてその等価性判定木を構成した様子である。q0,q2の遷移 から得られる等価性判定木の頂点q2とq3は等価でなくq2 .q3、とq1,q3の遷移からは等価性式 q₁ ≡q₁が得られる。このことから、q₀,q₂^{は等価でなく、}q₁,q₃のだけが等価であることが判定で きる。

これによって、1^{つの状態対}q1,q3を1つにまとめても機械が受理する入力文字列は変わらない ことがわかる。こうして同じ言語を受理する簡単化された機械M^′₄^を図5.11^{に示す。節}4.3^の正 規表現の表記では、M^′₄^{したがって}M4は正規言語(1+0(0+1))(0+1)^{∗を受理する。}

⓪q0 ≡q2

①q2.q3 ②q1≡q1

0

1

⓪q1≡q3

①q1≡q3 ②q3 ≡q1

0

1

図5.10 ^機械M4の状態対の等価性。状態q0とq2は等価でなく、q1とq3だけが等価で、機械 M4は1^{つの等価な状態対を}1つにまとめて同じ言語を受理する機械M^′₄^{を構成することがで} きる。

M^′₄ q0

start

q2

q1

0

1 0,1

0 1

図5.11 M4の1^{組の状態対}q1とq3をまとめて得られる等価な最小化機械M^′₄

M^′₁^およびM^′₄が受理する正規言語について 0^∗1(0+1)^∗ .(1+00+01)(0+1)^∗

である。実際、M^′₄^{が受理する入力文字列}00^をM^′₁は受理しない。したがって、図5.7^の機械M1

とM4は等価ではないことが示された。

演習5.5 ^図5.12^の機械Ma,M_b,Mc は全て同等であることを確かめなさい。この3^{つの機械が受} 理する言語の正規表現の同等性を示しなさい。

Ma q₀ start

q₁

q2

ε 0 1

0 1 0

1

Mb r0

start

r₁

r2

ε 0 1

1 0 1

0

Mc

s0 s1

ε 0,1

0,1

図5.12 ^機械Ma,Mb,Mcは同じ言語を受理する。