線形再帰方程式と正規表現

補題4.3 (Arden^の補題[15][16]) X,S,Tが正規表現であり、かつε<T ^のとき、X^{に関する線形} 再帰方程式は次の一意的解を持つ。

X=S+XT ^に対して X=ST^∗ X=S+TX ^に対して X=T^∗S

証明 言語集合に関する命題P={X =S+XT}^とQ={X=ST^∗}^{とが同値であることを}T =ϕ およびT ,ϕ^{の場合に分けて示す}[14]^。

(1) T =ϕ^{のとき。任意の言語}L^と空言語ϕ^{との連接が}Lϕ=ϕL=ϕ^およびϕ^∗ ={ε}^である ことから、XT = ϕ^よりP ={X =S}. ^一方、ST^∗ =Sε =S^よりQ = {X = S}. ^よって、

(2) T ,ϕ^のとき。

まず、Q→P^を示す。Q^{であるとき、}P^のX^{に代入すると、}X=S+ST^∗T =S(ε+T^∗T)=ST^∗ となり、P^はQ^に一致。

次にP →Q^{を示す。つまり、}P^{であるとき}ST^∗ ⊂ X ^かつX ⊂ ST^{∗ を示すことによって} X=ST^∗であることを証明し、そのことからQが成立することを示す。

（a^）P^{であることより、}S ⊂ X, XT ⊂ X ^{である。これより、}ST ⊂ XT ⊂ X. ^{したがって} ST²⊂XT^{となって、}ST² ⊂XT⊂X. ^{これを繰り返すと、}ST^∗⊂X^{が得られる。}

（b^）X^に含まれST^{∗ に含まれない集合}K ≡X−ST^{∗ が}K,ϕ^{と仮定する。}K^{に属する最} 短の語をw^{とする（当然、}w∈X^{である）。}w<ST^{∗ であることから}w<S^、よってP であることからw∈XT.

T ,{ε}^より、w^はあるu∈X^およびv∈T^を使って w=uv ^ただし、|u|<|w|

と書ける。しかし一方、w^はK⊂Xの最短の語であるので、|u|<|w|^であるu^はu<K であるので、u∈ST^∗でなければならない。これより、w=uv∈(ST^∗)(T)=ST^∗T⊂ST^∗. したがって、w ∈ ST^∗ であることになって、仮定w < ST^∗ に矛盾する。すなわち、

K=X =ST^∗ =ϕ^、X⊂ST^{∗ がわかった。}

(a), (b)^よりX=ST^{∗ が示され、}P→Q^{が証明された。}

■

例4.2 ^{アルファベット}Σ ={0,1}上の正規表現に関して、次のX,Y に関する線形再帰方程の解を 求めてみる[14, p.100]^。

(1) X=00+11+X0+X1 (2) X=01+X0^∗1

(3) X=0+X1^∗01+Y1(01)^∗,Y=X1

(4) X=11^∗0+X01+Y1,Y =11^∗+X0+Y1

補題4.3 ^とKleene^{演算に関する演習}4.1 を使う。正規表現の表式は語の集合であることに注意

する。

(1) (00+11)(0+1)^∗

(2) 01(0^∗1)^∗ =01(ε+0^∗1(0^∗1)^∗)=01+010^∗1(0^∗1)^∗ =01+01(0^∗1)^∗ =01+(0^∗1)^∗

(3) Y = X1 を代入すると、解くべき方程式X = 0^∗ +X(1^∗01+11(01)^∗)^{を得る。これより、}

X=0^∗(1^∗01+11(01)^∗)^∗,Y =0^∗(1^∗01+11(01)^∗)^∗1

(4) Y = (11^∗ +X0) +Y1 ^として Y ^{について解くと、}Y = (11^∗ +X0)1^∗ = 11^∗ + X01^{∗ を} 得る. ^これを X ^{の方程式に代入して、}X = 11^∗0+11^∗1 +X(01+ 01^∗1). ^{これを解い} て、X = 11^∗(0+ 1)(01+01^∗1)^∗ = 11^∗(0+1)(01^∗1)^∗. ^これを Y ^{の式に代入して、}Y =

11^∗(ε+11^∗(0+1)(01^∗1)^∗01^∗).

例4.3 ^図4.1^{の有限オートマトン}Ma,Mb,Mc,Mdが定める正規表現を求めてみる[14, pp.101–

102]^。

Ma

q0

start

q1

ε 0

1

Mb

q0

start

q1

ε 0

0,1

Mc

q₀ start

q₁ ε

1

0 0,1

Md

q0

start

q1

q2

ε

0 0

1 1

1

図4.1 オートマトンから正規表現を求める

有限オートマトンM =(Σ,Q, δ,q0,F)^{において、初期状態}q0から状態qk ∈ Q^{に遷移する入力} x∈Σ^{∗語の集合}R_kがすべて正規表現である。正規言語{Rk}同士に関する再帰方程式を補題4.3^を 使って解いて求める正規表現を得る。

a) ここでは簡単に、受理状態q₁^{に遷移するためには}0^回以上の1^{が続いた後に}0^{である記号} 列でなければならないと考えて、直ちに1^∗0^{を得る。形式的には、}R₀=ε+R₀1,R₁=R₀0 を連立させて解く（R₀=ε+1R₀ではないことに注意する）。補題4.3^よりR₀ =ε1^∗ =1^∗、 よってR₁=R₀0=1^∗0.

b) ここでは簡単に、受理状態q1に遷移するため1^回の0^の後は0^または1^が0^{回以上現れる} 記号列でなければならない考えて、直ちに0(0+1)^{∗ を得る。}R₀ =ε,R₁ =R₀0+R₁(0+1) を連立させる。R₁ =0R₀+R₁(0+1)^やR₁ =R₀0+(0+1)R₁などではないことに注意す る。R₁=0+R₁(0+1)^より、R₁=0(0+1)^∗.

c) ^状態q0とq1に遷移するための正規表現R₀^およびR₁^{は次の関係にある。}

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

補題4.3^より、R₀ =ε0^∗ = 0^∗. ^これをR₁^{の式に代入して、}R₁ =0^∗1+R₁(0+1). ^よって、

R₁=0^∗1(0+1)^{∗ を得る。}

d) ^状態q0,q1,q2に遷移するための正規表現R₀,R₁^およびR₂^{は次の関係にある。}

R₀=ε, R₁=R₀0+R₁1, R₂=R₀1+R₁1+R₂1

R₀^をR₁^{の式に代入して、}R₁=ε0+R₁0=0+R₁0.^補題4.3^より、R₁=00^∗. ^これらをR₂ の式に代入して、R₂=(1+00^∗1)+R₂1. ^{したがって、}R₂=(1+00^∗1)1^∗.

例4.4 有限オートマトンが受理する言語集合としての正規表現は一意には定まらない。図4.2^の有 限オートマトンMeが受理する言語の正規表現を考えてみよう。

Me

q0

start

q1

ε 1

1

0 0

図4.2 正規表現の形は一意的に定まらない

状態q0とq1に遷移するための正規表現R₀^およびR₁^{は次の関係にある。}

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

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

式(1)^をR₀=(ε+R₁1)+R₀0^{として、補題}4.3^より R₀=(ε+R₁1)0^∗

を得て、これを(2)^{に代入して次を得る。}

R₁=(ε+R₁1)0^∗1+R₁0=0^∗1+R₁(10^∗1+0) したがって、

R₁=0^∗1(10^∗1+0)^∗. (3)

一方、式(2)^からR₁=R₀10^{∗を得て、これを}(1)^{に代入して} R₀=ε+R₀0+R₀10^∗1=ε+R₀(0+10^∗1)

これより、R₀=ε(0+10^∗1)^∗ =(0+10^∗1)^{∗となる。}(2)^{に代入して、}R₁=(0+10^∗1)^∗1+R₁0. ^よって、

R₁=(0+10^∗1)^∗10^∗ (4)

以上から、Me が受理する言語の正規表現として、式(3)^および(4)の異なる表現が得られた。この ように、一般に代入に仕方には任意性があるために、得られる正規表現は様々になり、さらに、演

習4.1^のようにKleene閉包の表し方もいろいろあるために一意的とはならない。