5
任意の正則表現から、その正則表現の言語を受理言語とするε-NFAを作ることができます。
6
変換規則3 rをΣの上の任意の正則表現とします。そのとき、L(r)を受理言語とするε-NFA:
7
M = (Q,Σ,δ, q0, F)を必ず作ることができます。すなわち、記号列uについて、u∈L(r)ならば
8
u∈L(M)であり、u /∈L(r)ならばu /∈L(M)であるようなM が存在し、そのようなM を実際
9
に作ることができます。
10
具体的な変換方法として、正則表現rが、r=a(a∈Σ)、r=ε、r=∅の場合の変換方法を初
11
めに示します。次にr1、r2は正則表現であって、それぞれに対応するε-NFA:M1、M2が既に構
12
成されていると仮定します。このとき、r=r1 |r2、r=r1r2、r=r∗1、r= (r1)、r=r+1 の形を
13
しているときのオートマトンの構成法を示します。ただし、議論を簡単にするため、この変換規則
14
によって構成される全てのオートマトンでは、
15
1. 最終状態はひとつしか存在せず、
16
2. 最終状態を始点とする枝はなく、
17
3. 初期状態と最終状態は異なる
18
ように構成すると約束します。
19
1. まず、r=a(a∈Σ)ならば、対応するε-NFAを図8.1(1)のように作ります。このε-NFAを
20
5項組Maで示すと、Ma= ({q0, qf},Σ,δa, q0,{qf})です。ただしδa(q0, a) ={qf}とし、そ
21
れ以外のδaの値は全て∅です。
22
2. もしr=εならば、対応するε-NFAを図8.1(2)のように作ります。このε-NFAを5項組Mε
23
で示すと、Mε= ({q0, qf},Σ,δε, q0,{qf})です。ただしδε(q0,ε) ={qf}とし、それ以外の
24
δεの値は全て∅です。
25
q0 a qf
r=a
q0
ϵ
qfr=ϵ
q0 qf
r=∅
q0 qf
q0 qf
q0 qf
(1) (2) (3)
(4)
q0 qf
ϵ
q0ϵ ϵ ϵ
ϵ
qf
r=r
1|r
2r=r
1r
2(5)
r=r
1*q0 qf
ϵ
q0
ϵ
qfϵ
ϵ
(6)
1 1
1 1
1 1
2 2
2 2
図 8.1: 正則表現からε-NFAへの変換
3. もしr=∅ならば、対応するε-NFAを図8.1(3)のように作ります。このε-NFAを5項組M∅
1
で示すと、M∅= ({q0, qf},Σ,δ∅, q0,{qf})です。ただし遷移関数δ∅の値は全て∅です。
2
次に、r1、r2が正則表現であって、それぞれに対応するε-NFA:M1、M2が既に構成されている
3
と仮定します。ここに5項組をM1= (Q1,Σ,δ1, q10,{q1f})、M2= (Q2,Σ,δ2, q02,{qf2})と仮定して
4
おきます。
5
1. もしr=r1|r2ならば、対応するε-NFAを図8.1(4)のように作ります。このε-NFAを5項組
6
MAで示す1と、MA= (Q1∪Q2∪{q0, qf},Σ,δA, q0,{qf})です。ただしδA(q0,ε) ={q01, q20}、
7
δA(qf1,ε) = {qf}、δA(qf2,ε) = {qf}、任意の記号a ∈ ΣについてδA(q0, a) = δA(qf1, a) =
8
δA(qf2, a) =∅です。さらにM1の任意の状態q∈Q1、および任意の記号a∈Σ∪{ε}につい
9
てδA(q, a) =δ1(q, a)、M2の任意の状態q∈Q2、および任意の記号a∈Σ∪{ε}について
10
δA(q, a) =δ2(q, a)とします。
11
2. もしr=r1r2ならば、対応するε-NFAを図8.1(5)のように作ります。このε-NFAを5項組
12
MCで示す2と、MC= (Q1∪Q2,Σ,δC, q01,{qf2})です。ただしδC(qf1,ε) ={q20}です。さら
13
に任意の状態q∈Q1−{q1f}、および任意の記号a∈Σ∪{ε}についてδC(q, a) = δ1(q, a)、
14
任意の状態q∈Q2、および任意の記号a∈Σ∪{ε}についてδC(q, a) =δ2(q, a)とします。
15
3. もしr=r∗1ならば、対応するε-NFAを図8.1(6)のように作ります。このε-NFAを5項組
16
MKで示す3と、MK = (Q1∪{q0, qf},Σ,δK, q0,{qf})です。ただしδK(q0,ε) ={q10, qf}、
17
δK(qf1,ε) ={q01, qf}です。さらに任意の状態q∈Q1−{q1f}、および任意の記号a∈Σ∪{ε}
18
についてδK(q, a) =δ1(q, a)とします。
19
4. もしr= (r1)ならば、対応するε-NFAはM1と同じです。
20
5. もしr=r+1 ならば、これをr=r1r1∗またはr=r∗1r1に変形し、変換を行います。 "
21
例として正則表現(H|F|R)∗をε-NFAに変換することを考えましょう。まず、三つの正則表現
22
H、F、Rに対応するε-NFAはそれぞれ図8.2 (1)、(2)、(3)です。ただし煩雑ですから、各状態
23
にラベル(q0、qf など）は付けないことにします。次に、正則表現H|Fに対応するε-NFAは、図
24
8.2(1)、(2)の二つのε-NFAをもとに図8.1(4)のように組み上げて、図8.2(4)です。正則表現H|F|R
25
は(H|F)|Rと見なせますから、これに対応するε-NFAは、図8.2(4)、(3)のふたつのε-NFAを図
26
8.1(4)のように組み上げて、図8.2(5)です。そして正則表現(H|F|R)∗に対応するε-NFAは、図
27
8.2(5)のε-NFAをもとに図8.1(6)のように組み上げて、図8.2(6)です。これが求めるオートマト
28
1添字AはAlternation（選択）に由来して付けました。
2添字CはConcatenation（連接）に由来して付けました。
3添字KはKleene（クリーネ:人名）に由来して付けました。
H
r =H
(1)
(4)
ϵ ϵ ϵ
ϵ
r =H|F
F
r =F
(2)
R
r =R
(3)
F H
(5)
ϵ ϵ ϵ
ϵ
r =(H|F)|R=H|F|R
F H
R
ϵ ϵ
ϵ ϵ
(6)
ϵ ϵ ϵ
ϵ
r =(H|F|R)
*F H
R
ϵ ϵ
ϵ ϵ ϵ
ϵ
ϵ ϵ
図 8.2: 正則表現(H|F|R)∗のε-NFAへの変換
ϵ ϵ ϵ
ϵ
F H
R
ϵ ϵ
ϵ ϵ ϵ
ϵ
ϵ ϵ
H
F F
ϵ ϵ
ϵ
ϵ ϵ
ϵ ϵ ϵ
ϵ
F H
ϵ
ϵ ϵ
ϵ
ϵ
ϵ
図 8.3: 正則表現(H|F|R)∗(H|FF)(H|F)∗のε-NFAへの変換
ンです。オートマトンを構築していく操作が変換規則3に基づいた全く機械的なものであることに
1
注意してください。
2
同様の機械的な操作を繰り返すことで、正則表現(H|F|R)∗(H|FF)(H|F)∗に対応するε-NFAを
3
図8.3のように得ます。
4
ところで、正則表現(H|F|R)∗(H|FF)(H|F)∗は缶ジュースが出てくる記号列の集合を表現したも
5
のでした。7章では、そのような記号列の集合を表すε-NFAとして図7.1を示しました。このオー
6
トマトンを変換規則3に基づいて求めた図8.3と比較すると、その形状は相当に異なります。一言
7
で言えば、図8.3の方が多くのε-遷移を含み、
冗長
です。6章の変換規則1、7章の変換8
規則2もそうでしたが、自動変換して導出されたオートマトンは、人手で求めたオートマトンより
9
も冗長です。冗長ですが、しかし受理言語は同じです。
10
また、図8.3には多くのε-遷移が使用されていますが、それらがオートマトンの部品と部品をつ
1
なぐ役割を果たしている事に気づくでしょう。ε-遷移は、正則表現から有限状態オートマトンへの
2
変換を容易にするために導入されました4。
3
変換規則1、変換規則2がそうであったように、変換規則3が等価変換であることも証明せねば
4
なりません。それにはやはり数学的帰納法5を用います。この証明は図8.1からほとんど明らかで
5
あるため、このテキストでは省略します。
6