オートマトン・形式言語及び演習
— 3.正規表現—
酒井 正彦
www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/
3- 1 / 29
正規表現とは
正規表現(正則表現, Regular Expression)
オートマトン：言語を定義する機械
正規表現：言語を記号列で定義
- 記述しやすい(ユーザフレンドリ)
例：01∗
+ 10∗
- UNIX の grep コマンド
- UNIX の lex, flex ツールの入力の記述
3- 2 / 29
準備
言語上の演算
和：集合の和と同じ
L ∪ M = {w | w ∈ Lまたは
w ∈ M}
連接：
L M = {w | w = x y, x ∈ L, y ∈ M}
(L Mは
L.Mとも書く)
ベキ：
L0
={ε}, L1
=L, Lk+1=L.Lk
クリーネ閉包：
L∗
=[∞
i=0
Li
問：∅0
, ∅i, ∅∗
はどんな集合？
3- 3 / 29
準備
補題1: 任意の言語
M, N, Pに対して、以下が成り立つ
(
MN)P = M(NP)
証明：文字列
x, y, zに対して(
xy)z = x(yz)が成り立つこと
から証明できる
補題2: 任意の言語
Mに対して、
MiMj=
Mi+jが成り立つ
証明：
iに関する帰納法で示す
-
i = 0のときは明らか
-
i > 0のとき、
左辺
=(MMi−1)
Mj=
M(Mi−1Mj)
=
M(Mi+j−1)=右辺
正規表現
正規表現
Eとそれが表す集合
L(E)の再帰的定義
基底：
- εは正規表現で、
L(ε) ={ε}
- ∅は正規表現で、
L(∅) ={ }
-
a ∈ Σ のとき、
aは正規表現で、
L(a) =
{a}
帰納：
E, Fが正規表現のとき、
- (
E)は正規表現で、
L((
E)) =
L(E)
-
E+
F は正規表現で、L(E+
F) = L(E) ∪ L(F)
-
E.
F は正規表現で、L(E.
F) = L(E).L(F)
-
E∗
は正規表現で、L(E∗
) = (L(E))∗
正規表現
例：0と1が交互に現われる文字列全体を表す正規表現
(01)∗
+ (10)∗
+ 0(10)∗
+ 1(01)∗
別の表現も可能
(ε + 1)(01)∗
(ε + 0)
演算の優先順序
∗,.,+(結合の強い方から順に)
例：01∗
+ 1は(0(1∗
)) + 1を表す
正規表現
性質の例：
任意の正規表現Eに対して、L(E∗E∗) =L(E∗)が成り立つ
証明：L(E∗E∗) = (L(E))∗.(L(E))∗より、任意の言語Mに対
してM∗M∗=M∗を示せば十分である。
w ∈ M∗ならばw ∈ M∗M∗は、ε∈ M∗より明らか
w ∈ M∗M∗ならばw ∈ M∗を証明する
I w ∈ M∗M∗とすると、w ∈ MiMjを満たすi, j が存在
する
I スライドp.3-4 の補題 2 より w ∈ Mi+jであるから、
w ∈ M∗
3- 7 / 29
有限オートマトンと正規表現
有限オートマトンと正規表現の等価性の証明手順
3- 8 / 29
有限オートマトンから正規表現への変換
定理3.4:任意の
DFA A = (Q, Σ, δ, q0,
F)について、
L(R) = L(A)を満たす正規表現
Rが存在する
証明：
Aの状態を
{1, 2, . . . , n}、初期状態を1とする
Aの状態
iから
jに至る経路(文字列)で、
kより大きな
状態を経由しない文字列全体を表す正規表現を
Rij(
k)で
表す
3- 9 / 29
有限オートマトンから正規表現への変換
証明（続き）：
R(
k)
ij が分かれば、
L(R) = L(A)を満たす
Rは、
R1(
n)j の和
(ただし、
jは全ての受理状態)で与えられる
R(
k)
ij の
kに関する再帰的定義
基底：
i 6= j かつ δ(i, a) = j を満たす a を a1,
a2, . . . ,
amとする
とき、
R(0)
ij =
a1+
a2+· · ·+
am
ただし、
m = 0 のとき、Rij(0)=∅
i = j かつ δ(i, a) = j を満たす a を a1,
a2, . . . ,
amとする
とき、
R(0)
ij =
a1+
a2+· · ·+
am+ ε
3- 10 / 29
有限オートマトンから正規表現への変換
証明（続き）：
R(
k)
ij の
kに関する再帰的定義(続き)
帰納：
R(
k)
ij =
Rij(
k−1)+
Rik(
k−1)(
Rkk(
k−1))∗
Rkj(
k−1)
3- 11 / 29
有限オートマトンから正規表現への変換
例：次のDFAが認識する言語を表す正規表現を構成する
まず、
Rij(0)を求める
3- 12 / 29
有限オートマトンから正規表現への変換
以降で使う、正規表現の簡単化の規則
-
R(S + T)=
RS + RT
- (
S + T)R=
SR + TR
-
R∗
(ε +R)=R∗
=(ε +R)R∗
-
Ri+R∗
=R∗
- (ε +
R)∗
=R∗
-
R + RS∗
=RS∗
- ε∗
=ε
-
∅R=
R∅=∅
-
∅ + R =
R + ∅=
R
3- 13 / 29
有限オートマトンから正規表現への変換
次に
Rij(1)を求める
R(1)
ij =
Rij(0)+
Ri1(0)(
R11(0))∗
R
(0)
1
j
3- 14 / 29
有限オートマトンから正規表現への変換
次に
Rij(2)を求める
R(2)
ij =
Rij(1)+
Ri2(1)(
R22(1))∗
R
(1)
2
j
3- 15 / 29
有限オートマトンから正規表現への変換
よって、
得られた正規表現は、
R(2)
12 =1∗0(0 + 1)∗
有限オートマトンから正規表現への変換
II
状態消去法：
ラベルを正規表現に拡張したオートマトンを考え、状
態を消去する(前回の方法より効率的)
有限オートマトンから正規表現への変換
II
状態
sを消去する
有限オートマトンから正規表現への変換
II
各々の受理状態
qについて、
qと
q0以外の状態を全て消去
する
q 6= q0なら、対応する正規表現は(
R+
SU∗
T)∗
SU∗
q = q0なら、対応する正規表現は
R∗
求めたい正規表現は、これらの和
3- 19 / 29
有限オートマトンから正規表現への変換
II
例：最後の2文字目か3文字目に1を持つ列を受理するオー
トマトン
ラベルを正規表現に変更
状態
Bを消去
3- 20 / 29
有限オートマトンから正規表現への変換
II
例(続き)：
状態
Cを消去し、(0 + 1)∗
1(0 + 1)(0 + 1)を得る
状態
Dを消去し、(0 + 1)∗
1(0 + 1)を得る
3- 21 / 29
有限オートマトンから正規表現への変換
II
例(続き)：
以上から、
(0 + 1)∗
1(0 + 1)(0 + 1) + (0 + 1)∗
1(0 + 1)
を得る
3- 22 / 29
正規表現からオートマトンへの変換
定理3.7:任意の正規表現
Rについて、
L(A) = L(R)を満た
すε-NFAが存在する
証明：
Rの構成に基づいて帰納的に
Aを定義する
基底：ε、∅、
aと等価なオートマトンは、以下の通り
3- 23 / 29
正規表現からオートマトンへの変換
定理3.7の証明(続き)
帰納：
R + S、
RS、
R∗
と等価なオートマトンは、以下
の通り
3- 24 / 29
正規表現からオートマトンへの変換
例：(0 + 1)∗
1(0 + 1)と等価なε-NFA
を作る
3- 25 / 29
正規表現の代数的法則
結合法則と交換法則
-
L + M=
M + L
-
L + (M + N)=(
L + M) + N
-
L(MN)=(
LM)N
-
LM6=
ML
単位限と零元
-
∅ + L=
L + ∅=
L
- ε
L=
Lε=
L
-
∅L=
L∅=∅
3- 26 / 29
正規表現の代数的法則
分配法則
-
R(S + T)=
RS + RT
- (
R + S)T=
RT + ST
冪等法則
-
R + R=
R
閉包に関する法則
- (
R∗
)∗
=R∗
- ∅∗
=ε
- ε∗
=ε
-
R+
=RR∗
=R∗
R
-
R∗
=R+
+ ε
3- 27 / 29
正規表現の代数的法則
正規表現に関する法則の発見・検証(機械的)
- 例：
Eと
Fを正規表現とするとき、
E+
F = F+
E
を示す方法
-
Eを
aに、
Fを
bに固定する
-
L(a + b) =
L(b + a)を自動検証する(４章)
この手法は、+、.、∗の演算のみを使う限り正しい。(集合
の積では成立しない。教科書p.135の囲み記事を参照)
正規表現の代数的法則
例：(
E+
F)∗
=(E∗
F∗
)∗
の証明には、(a + b)∗
と(a∗
b∗
)∗
の等
価性を示せば十分である。
例：
E∗
=E∗
E∗
の証明には、a∗
とa∗
a∗
の等価性を示せば十
分である。
問：
E+
FE=(
E+
F)
Eは成立するか？
