m – 1

講義URL:
http://www.kono.cis.iwate-u.ac.jp/~yamanaka/Lecture/Automata/index.html
※ 文字化けしてしまう場合はブラウザのエンコードを変更してみて下さい
形式言語とオートマトン
第5回
山中克久
目次
復習: 正規表現の基本
l  正規表現 à 非決定性有限オートマトン
l  反復補題
l 
正規表現と似たもの: Unixコマンド
正規表現
記号列のパターンを記述したもの
正規表現に似た概念が使われる例
⇒ UNIX のコマンド
「rm （remove）」コマンド
ディレクトリ内の txtファイルを一気に消したいとき
% rm *.txt
「メタ文字」という特別な意味をもつ文字がある
正規表現の例
正規表現
記号列のパターンを記述したもの
正規表現の例
a（ba）* a + b（ab）* b
* : 0回以上の繰り返し
+ : または
言葉で説明すると
a のあとに，ba が0回以上現れて，最後に a が現れる，
または，b のあとに，ab が0回以上現れて，最後に b が出現
上の正規表現で表されている系列の例：
aa, abababaa, bb, babababb
正規表現の定義
再帰的に正規表現（regular expression）を定義
（1） a1,…, ak, ε, Φ は正規表現
（2） r と s が正規表現ならば，（r+s）, (r・s), （r*）は
いずれも正規表現
+ : 和集合（または），
・ : 連接（前後をつなげる），
* : 連接閉包（0回以上現れる）
正規表現の例:
a（ba）* a + b（ab）* b
正規表現の定義
再帰的に正規表現を定義
（1） a1,…, ak, ε, Φ は正規表現
（2） r と s が正規表現ならば，（r+s）, (r・s), （r*）は
いずれも正規表現
先の例「a（ba）* a + b（ab）* b」は正規表現だろうか?
+
・
a（ba）* a
・
a（ba）*
・
a
a（ba）* a + b（ab）* b
b（ab）*
・
*
・
（ba）*
ba
b
a
a
*
・
a
b
b（ab）* b
a
（ab）*
ab
b
よって
正規表現である!
b
正規表現によって表される言語
正規表現: r = a（ba）* a + b（ab）* b
r によって表される言語:
L（r） = {aa, bb, abaa, babb, ababaa, … }
= { w ∊ {a,b}* | a のあとに，ba が0回以上現れ
て，最後に a が現れる，または，b のあとに，
ab が0回以上現れて，最後に b が出現する
ような w }
※正規表現によって表される言語（文字列の集合）を
正規言語と呼ぶ
例3.2
具体的な正規表現を等式の左辺で与え，それが表す
言語を右辺で説明する
（0+1）* 110 （0+1）*
= {w | w は 110 を部分系列として含む}
（0+1）（0+1）（0+1）（0+1）* = { w | wの長さは3以上}
0+1+0 （0+1）* 0 + 1（0+1）* 1
= { w | w の初めと終わりの記号は同じ}
0* 1* 2* = { 0i 1j 2k | i ≧ 0，j ≧ 0，k ≧ 0 }
NFA à 正規表現
定理3.18
任意の正規表現に対して，それが表す言語を受理
する非決定性有限オートマトンが存在する
start
q1
ε
1（0+1）* 1
正規表現
q0
1
1
start
ε
0 q
ε
ε q4
6
q3
q8
ε q5 1 q7 ε
NFA
0,1
q2
q0
1
q1
1
簡単化した
NFA
q2
証明のアイデア
定理3.18
任意の正規表現に対して，それが表す言語を受理
する非決定性有限オートマトンが存在する
P（m）: 現れる演算記号が m 個以下の正規表現 r に対し，
等価な非決定性有限オートマトンで，受理状態が
1個のものが存在する
帰納法で証明
1. P（0）を証明
2. P（m-1）を仮定して P（m）を証明する
P（0）の証明
P（0）: 現れる演算記号が 0 個以下の正規表現 r に対し，
等価な非決定性有限オートマトンで，受理状態が
1個のものが存在する
(i) ε
ε
(ii) Φ
(iii) a ∈ Σ
M（ε）
M（Φ）
a
M（a）
P（m – 1）を仮定してP（m）を証明
P（m – 1）が成立すると仮定する
P（m）: 現れる演算記号が m 個以下の正規表現 r に対し，
等価な非決定性有限オートマトンで，受理状態が
1個のものが存在する
r+s に対応
各演算ごとに考える: 集合和（+）
M（r）: r と等価なNFA
M（r）
start
start
start
M（s）: s と等価なNFA
ε
ε
ε
ε
M（s）
P（m – 1）を仮定してP（m）を証明
P（m – 1）が成立すると仮定する
P（m）: 現れる演算記号が m 個以下の正規表現 r に対し，
等価な非決定性有限オートマトンで，受理状態が
1個のものが存在する
各演算ごとに考える: 連接（・）
M（r）
rs に対応
start
M（r）
start
start
M（s）
ε
M（s）
P（m – 1）を仮定してP（m）を証明
P（m – 1）が成立すると仮定する
P（m）: 現れる演算記号が m 個以下の正規表現 r に対し，
等価な非決定性有限オートマトンで，受理状態が
1個のものが存在する
各演算ごとに考える: 閉包（*）
start
M（r）
start
ε
ε
M（r）
全ての演算に対してP（m）が成立することが示せた
例で試す
正規表現: 1（0+1）* 1
Step 1
1
start
0
start
Step 2
1
start
0
ε
start
start
ε
ε ε
start
ε
start
ε
1
ε
ε
ε
0
ε
1
ε
start
1
start
1
ε
0
ε
1
ε
Step 4
1
ε
start
1
ε
start
1
ε
Step 3
1
start
1
ε
Step 5
start
ε
1
ε
ε
ε
ε
0
1
ε ε
1
ε
正規表現と有限オートマトンの等価性
系3.21
非決定性有限オートマトンで受理される言語は，
正規表現で表される
証明略（教科書参照）
非決定性有限オートマトンで受理される言語と，
正規表現で表される言語は等価である
まとめ
非決定性有限オートマトンで受理される言語と，
正規表現で表される言語は等価である
正規表現で表
される言語か
らなる集合
=
NFAで受理さ
れる言語から
なる集合
=
DFAで受理さ
れる言語から
なる集合
練習問題
練習問題5-1
例3.2 に出現した正規言語と同じ言語とを受理する有
限オートマトンを書け．決定性有限オートマトンでも非
決定性有限オートマトンでもかまわない
（0+1）* 110 （0+1）*
= {w | w は 110 を部分系列として含む}
（0+1）（0+1）（0+1）（0+1）* = { w | wの長さは3以上}
0+1+0 （0+1）* 0 + 1（0+1）* 1
= { w | w の初めと終わりの記号は同じ}
0* 1* 2* = { 0i 1j 2k | i ≧ 0，j ≧ 0，k ≧ 0 }
正規言語ではない言語
疑問
以下の言語は正規言語だろうか?
{ 0n 1n | n ≧ 1 }
正規言語: 正規表現で表される言語
復習: 正規表現
（1） a1,…, ak, ε, Φ は正規表現
（2） r と s が正規表現ならば，（r+s）, (r・s), （r*）は
いずれも正規表現
正規言語ではない言語
疑問
以下の言語は正規言語だろうか?
{ 0n 1n | n ≧ 1 }
à No
（個人的）直感的な理由:
正規表現で許されている演算で「個数を指定すること」
ができないから上記の言語は正規言語でない
「正規言語でないこと」をどのように証明したらよいか?
反復補題
定理3.22
Σ 上の正規言語 L に対して次の条件を満たす正整数 m
が存在する．すなわち，長さが m 以上の任意の系列 w ∊ L
は，適当な x,y,z ∊ Σ* が存在して w = xyz と表されて，
次の3つの条件を満たす．
（1）任意の i ≧ 0 に対して，xyiz ∊ L
（2） |y| ≧ 1
w
∊L
（3） |xy| ≦ m
x
y
≦m
z
正規言語でないことの証明
例3.23
以下の言語が正規言語でないことを示せ
L = { 0 n 1n | n ≧ 1 }
証明
背理法による．L は正規言語であると仮定する．
{ 0n 1n | n ≧ 1 } の任意の系列 w について，定理
3.22（反復補題）の条件を満たす m が存在する
w = 0m1m とし， w について見ていく
例3.23
以下の言語が正規言語でないことを示せ
L = { 0 n 1n | n ≧ 1 }
証明
w = 0m1m ∊ L とし， w について詳しく見ていく
（1）任意の i ≧ 0 に対して xyiz ∊ L，（2） |y| ≧ 1，（3） |xy| ≦ m
w = 00000000000001111111111111
x
y≠ε
z
≦m
ここで，xy0z = xz は，0の個数と1の個数が異なる
ので xz ∉ L である．これは反復補題に矛盾する
正規言語でないことの証明その2
例3.24
以下の言語が正規言語でないことを示せ
L = { w ∊ {0,1}* | N0（w） = N1（w） }
N0（w）: w に含まれる 0 の個数
N1（w）: w に含まれる 1 の個数
証明
背理法による．L は正規言語であると仮定する．
L中の任意の系列 w について，定理3.22（反復補
題）の条件を満たす m が存在する
w = 0m1m とし， w について見ていく
以下の言語が正規言語でないことを示せ
L = { w ∊ {0,1}* | N0（w） = N1（w） }
N0（w）: w に含まれる 0 の個数
N1（w）: w に含まれる 1 の個数
証明
w = 0m1m ∊ L とし， w について詳しく見ていく
（1）任意の i ≧ 0 に対して xyiz ∊ L，（2） |y| ≧ 1，（3） |xy| ≦ m
w = 00000000000001111111111111
x
y≠ε
z
≦m
ここで，xy0z = xz は，0の個数と1の個数が異なる
ので xz ∉ L である．これは反復補題に矛盾する
練習問題
練習問題5-2
以下の言語が正規言語でないことを，（例えば，
教科書の例3.23 のように）きちんと示せ
L = { ww | w ∊ {0,1}* }
※ L中の任意の系列では，同じ系列が2回出現する

Download Report