文字列の同値類

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は同じ言語を受理する。

状態対の等価性判定は与えられたDFA^{を最小化する}1つの方法を示していた。DFAM^を最小化 して得られたM^′は、同型を除いて一意に定まるだろうか。ここでは、DFA^{の等価性を入力文字} 列の同値関係の観点から改めて考えてみよう。

命題5.2 (^{入力の同値関係}) DFAM =(Q,Σ, δ,q0,F)^{において、入力文字列}x,y ∈Σ^{によって同じ} 最終状態に到達することによってM^{で定まる関係}RMを

x RMy≡ ifδ(q0,x)=δ(q0,y) forx,y∈Σ^∗

で定義する。RMはΣ^∗ 上の同値関係で、その同値類の数は有限個である。

証明 RMが同値関係であることは次の3つの関係を確かめればよい。

(1) ^{同じ文字列}xは同じ状態に到達して、x RMx^{であるので、}RMは反射的。

(2) y^がx^{と同じ状態に到達して}x RMy^ならば、x^はy^{と同じ状態に到達して}y RMx^。よって x RMy→y RMx^となり、RMは対称的。

(3) y^がx^{と同じ状態に到達して}x RMy^、z^がy^{と同じ状態に到達して}y RMz^ならばz^はx^と 同じ状態に到達してx RMz^。よってx RMy∧y RMz→x RMz^となり、RMは推移的。

同値関係RMの定める同値類は到達状態p∈Q^{によって決まる}⟦p⟧Mであり、p^{に到達する入力語} の集合

⟦p⟧M={x∈Σ^∗|δ(q0,x)=p}

を定め、x ∈⟦p⟧Mである入力列は全て状態pに到達する。逆に、状態p^{に到達する}1^{つの入力文} 字列x∈Σ^∗は関係RMによって同値類[x]M

[x]M={y|x RMy,y∈Σ}

を定めて⟦p⟧Mに一致する。したがって、1^つの状態pに対応する入力語集合の同値類⟦p⟧Mとp に到達する入力列x^{を代表元とする同値類}[x]Mと1^対1^{に対応する。}

同値関係RMの定める同値類の個数はDFAMの状態の個数に等しく有限で、入力文字列全体 Σ^∗は有限個の同値類に直和分割される。

Σ^∗ =⊕

pi∈Q

⟦pi⟧M.

■ 命題5.3 DFAM = (Q,Σ, δ,q0,F)^の関係RMは、x RMy^{のとき任意の}z∈ Σ^{∗ に対して}xz RMyz が成立する。

証明 x RMy^なら入力x^と y^{は同じ状態}δ(q0,x) = δ(q0,y)に到達しているため、そこから任 意のz ∈ Σ^∗ が入力されたとしても再び同じ状態δ(q0,xz) = δ(q0,yz) に遷移する。したがって、

xz RMyz^である。 ■

定義5.7 (^右不変性) ^関係R^が演算◦^に対して x R y ⇒ x◦z R y◦z

であるとき、関係R^は右不変(right invariant)^{であるという。}DFA M^{による関係}RMは入力文字 列の連接に関して右不変な同値関係である。

命題5.2の証明からわかったように、入力文字列x,y∈ Σ^のMによる最終状態によって定まる DFAM^{の同値関係}RMの同値類は有限個で、入力文字列全体Σ^∗ を最終状態によって直和分割し たものである。言い換えれば、M^{の受理言語}L(M)^{はその受理状態}p_i ∈F^で定まるR_M^の同値類

⟦pi⟧Mの直和 L(M)=⊕

pi∈F

⟦pi⟧M

で表すことができる。この受理状態で定まる各同値類[pi ∈F]Mは正規表現で表されている。

例5.4 ^図5.13^{の左側の機械}M1で定義される同値関係RM1を考えよう。M1の3^つの状態q0,q1,q2

に対して、初期状態q0に到達する任意の入力文字列をたとえばε^、q2に到達する任意の入力文字 列をたとえば代表元1^、q2に到達する任意の入力文字列をたとえば代表元11^{として、それぞれの} 同値類を[ε]M1, [1]_M1, [11]_M1 ^とする。

これらの同値類はM1の状態q0,q1,q2と1^対1^{の関係にあり、}⟦q0⟧M1 =[ε]M1. ⟦q1⟧M1 =[1]_M1,

⟦q2⟧M1 =[11]_M1 であることに注意する。

M1

q0

start

q1 q2

ε

0 1

0 1

0 1

≡ M₂

r0

start

r1

ε

0

1

1 0

図5.13 ^等価なM^とM^′

これらの同値類は次のような文字列集合をなし [ε]M1 ={ε,0,00, . . . ,0ⁿ, . . .},

[1]_M1 ={1,10,100, . . . ,10ⁿ, . . .},

[ε]M1 は記号1^{を含まない}0^{個以上の記号}1^{からなる集合、}[1]_M1 ^は記号1^を1^{度だけ含む}01^文字 列、[11]_M1 ^は記号1^を2^度含む01文字列である。入力文字列全体Σ^∗はこれらの同値類に直和分 割される。

{0,1}^∗ =[ε]M1 ⊕[1]_M1⊕[11]_M1.

M1が受理する言語L(M1)は、受理状態から定める同値類の直和 L(M1)=[ε]_M1⊕[11]_M1

で表される。

一方、図5.13^{の右側の機械}M2は、演習5.6^{の方法によって}M1と等価M1≡M2であることを 示すことができる。M1の場合と同様にして、⟦r0⟧M2 =[ε]M2 および⟦r1⟧M2 =[1]_M2 ^{を考えること} ができ

{0,1}^∗ =[ε]M2 ⊕[12]_M2

と表すことができるが、M2が受理する言語L(M2)^{はその受理状態}r1から L(M2)=[ε]_M2

である。M₁^とM₂^{の等価性から、}L(M₁)=L(M₂)^{であることから、}

[ε]_M1⊕[11]_M1 =[ε]_M2, [1]_M1 =[1]_M2

となり、RM1 の同値類はRM2 の同値類に含まれるRM1 ⊂RM2 ことがわかった。このような事情 は、ある機械Mをより少ない状態を持つ機械M^′に簡略化する際に常に生じる。DFAM^の言語定 義はDFAの状態定義に依存し、一般的には互いに等価な冗長な状態が存在し、等価な状態同士を 合併させた状態とするM^′を構成すると、対応する同値類も合併されて合併された状態の同値類と なる。いいかえると元のM^{の同値類は}M^{′の細分になる。}

演習5.6 ^図5.13^の機械M1とM2が等価であることを節5.3の等価性判定木を構成して確かめな さい。また、M1の状態対q0とq2が等価であることを節5.4の等価性判定木の方法で確かめ、こ れらを1^{つにまとめて等価な}M2が得られることを示しなさい。

5.6 Myhill-Nerode ^の定理

Σ^上の言語L^{が与えられると、}x,y∈Σに対して常に次のような同値関係RL が定まる。

命題5.4 (^言語L^{が定める同値関係}) Σ^上の言語L^{に対して、任意の}x,y∈Σ^{∗ に関して関係}RL を x RLy≡ if^全てのz∈Σ^{∗に対して}xz∈L^かつyz∈L^{が成立、または}xz<L^かつyz<L^が成立. で定める。関係RL はΣ^∗ 上の右不変な同値関係である。

証明 RLが同値関係であることを、x,y,z∈Σ^{について次の}3つの関係が成立することで確か める。

(1) x RLxの成立は明かであるのでRL は反射的。

(2) xw,yw^が共にLに属するか属さなければ、yw,xw^も共にLに属するか属さないことから x RLy→y RLx^{となって、}RLは対称的。

(3) xw,yw^が共にLに属するか属さなくて、さらに yw,zw^も共にLに属するか属さないがで あればxw,zw^は共にLに属するか属さない。よって、x RLy∧y RLz→x RLz^となり、RL

は推移的。

同値関係RLは、x RLy^{なら任意の}w^{の連接についても}xw RLywであるので右不変である。 ■ RLはΣ^∗上の同値関係であるので、その同値類によってΣ^∗ を直和分割する。より正確には、次 の定理5.3^{が成り立つ。}Lが正規言語であればこの同値類の個数は有限で、L^はRLの同値類の有 限和で表されるというものである。

定理5.3 (Myhill-Nerode) Σ^上の言語Lに対して定義される左不変な同値関係をRLとするとき、

以下の命題は互いに同等である。ここで、同値関係の指数とはその同値類の濃度である。

(1) Lは正規言語（有限オートマトンの受理集合）である。

(2) Lは、有限指数を持つ右不変な同値関係Rのその幾つかの同値類の直和として表される。

(3) ^同値関係RL の指数は有限である。

証明 (1)→(2)

L^{を受理する}FA^をM=(Q,Σ, δ,q0,F)とする。これにより関係R^を xRy⇌δ(q0,x)=δ(q0,y), x,y∈Σ

で定義する。命題5.2 ^から、R は同値関係である。また、任意の x,z ∈ Σ ^に対して δ(q,xz) =

δ(δ(q,x),z)^{であることが、}xの長さに関する帰納法からわかる。これより、

xRy⇌δ(q0,x)=δ(q0,y)

⇌δ(δ(q0,x),z)=δ(δ(q0,y),z)

⇌δ(q0,xz)=δ(q0,yz)

⇌xzRyz=xzRyz.

z∈Σは任意であるために関係Rは右不変な同値関係である。さらにx∈L^{とすると、}δ(q0,x)∈F でしかもδ(q0,x)=δ(q0,y)^より、y∈L^となってy^はR^の同値類[x]Mに属し、命題5.4^からL^は 右不変同値関係RLを定める。これより、L^{は受理状態}F^{に達する文字列}x^（δ(q0,x))∈F^）の和と して定まる右不変同値関係R^{の和である。}

R^を(2)^満たすxRyである右不変同値関係とすると、任意のz∈Σ^{∗に対して}xzRyz^{となって、}

xz∈L⇌yz∈L

と、xz,yz^は共にLに属するかまたは属さないかのいずれかである。これよりxRLy^が成立。x^が 属する同値関係R^{の同値類の各要素は、}x^{の属する同値関係}RLの同値類に含まれることから、R によるΣ^{∗の同値類の分割は、}RL による分割の細分になっている。すなわち、Σ^{∗ の同値関係}R^に よる同値類全体をΣ^∗/R^{、同値関係}L^{による同値類全体を}Σ^∗/RLとしたとき、

|Q|≧|Σ^∗/R|≧|Σ^∗/RL|=|Q^′| Q^{′は以下で定義される}FA^{の状態集合} (5.1) となる。Rによる分割が有限個であることより、RL の指標も有限になる。

(3)→(1)

同値関係RL による同値類の有限集合をQ^′とし、その代表元を文字列x^とすると Q^′={[x]RL|,x∈Σ}.

また、

δ^′([x]RL,a)=[xa]RL, q^′₀=[ε]_RL,

F^′ ={[x]RL|x∈L}

と定めると、M^′ = (Q^′,Σ, δ^′,q^′₀,F^′)は有限オートマトンになる。δ^{′は代表元}x^{の選び方に依らな} い。実際、xRLy^{であるとき、}RL の右不変性からxaRLyz^となって[xa]RL =[ya]RLである。

さて、

δ^′(q^′₀,x)=δ^′([ε]RL,x)=[εx]RL =[x]RL

より、

x∈L(M^′)⇌[x]RL ∈F^′

⇌x∈L

である。したがって、L(M^′)=L^となる。 ■

5.6.1 Myhill-Nerode ^の応用

Myhill-Nerode^の定理5.3をつかって、ある言語の非正規性、どんな有限オートマトンを工夫し

ても受理できない言語を証明することができる。

例5.5 Σ ={a,b}^上の言語L={aⁿbⁿ|n≧0}^{は正規言語ではない。}

もしL^{が正規言語であれば}, Myhill-Nerode^{の定理から、}Lで定まる右不変な同値関係RLによ るΣ^∗の分割は有限指数を持ち、

a^jRLa^k

であるような整数j<kが存在する。このとき、右不変性から a^jbⁱRLa^kbⁱ

となる（a^jbⁱ,a^kb^{iがどちらも}Lに属するか、またはどちらもLに属さないかいずれかである）。し かし、a^jbⁱ ∈ L^のときa^kbⁱ ∈ L^になりLの定義に反する。したがって、L^{は正規言語ではあり得} ない。

この有名なLの非正規性は正規言語の反復補題4.6によっても示すことができる。

節5.6^の定理5.3^の証明の(2)→(3)^にある式(5.1)^{は、証明の}(3)→(1)で構成するオートマトン の状態集合Q^′の個数（与えられた有限オートマトンM^{で受理される言語}L^{が定める同値関係}RL

によるΣ^{∗の同値類への分割個数}|Q^′| =|Σ^∗/RL|^{）は、言語}Lを受理する有限オートマトンM^の最 小値を与えている。

ドキュメント内 version 0.9 (ページ 66-72)