印刷用

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