オートマトン形式言語及び演習 4. 正規言語の性質酒井正彦正規言語の性質反復補題正規言語が満たす性質ある与えられた言語が正規言語でないことを証明するためにその言語が正規言語であると

Size: px

Start display at page:

Download "オートマトン形式言語及び演習 4. 正規言語の性質酒井正彦正規言語の性質反復補題正規言語が満たす性質ある与えられた言語が正規言語でないことを証明するためにその言語が正規言語であると"

きのこなかじゅく
4 years ago
Views:

オートマトン形式言語及び演習 4. 正規言語の性質酒井正彦 www.trs.css.i.nagoya-u.ac.

言語 L 01 = {0 n 1 n n 1} が正規言語と仮定する L 01 を認識する DFA が存在するその状態数を k としよう k + 1 種類の入力 ε, 0, 00,.

1 オートマトン形式言語及び演習 4. 正規言語の性質酒井正彦正規言語の性質正規言語が満たす性質ある与えられた言語が正規言語でないことを証明するためにその言語が正規言語であると仮定してを使い矛盾を導く閉包性正規言語を演算により組み合わせて得られる言語が正規言語となる演算について調べる複雑なオートマトンを構成するツールとして利用可能状態数の減少技術実現するチップ面積の減少の直観的説明言語 L 01 = {0 n 1 n n 1} が正規言語と仮定する L 01 を認識する DFA が存在するその状態数を k としよう k + 1 種類の入力 ε, 0, 00,..., 0 k を考えると状態数が k なので同じ状態にたどり着く入力が少なくとも 2 種類存在するその状態を q, 二つの入力を 0 i 0 j (i j) とする 0 i 1 i は受理されるので q から受理状態へ 1 i でたどり着けるしたがって 0 j 1 i も受理してしまい矛盾する 4-1 / / / 27 定理 4.1: ( 正規言語に対する ) L を正規言語とするとき n > 0 が存在して w n なる任意の w L についても以下を満たす分解 w = xyz がある 1. y ε 2. xy n 3. k 0, xy k z L 証明 :L を認識する DFA が存在するのでその状態数で n を定める w = a 1 a 2... a m L, m n p i = δ(p 0, a 1 a 2 a i ) (i = 0,... m) とすると p i = p j, (i < j) を満たす i, j が存在する ( 最小の i, j を選ぶ ) 図のように x, y, z を定めると y ε かつ xy n かつ k 0, xy k z L 例 : を利用して L eq (0 と 1 の出現数が等しい文字列からなる言語 ) が正規言語でないことを示す - L eq が正規言語と仮定 - で定まる n から w = 0 n 1 n L eq を決める - y ε, xy n, k 0, xy k z L eq を満たす分割 - y = 0 m (0 < m) より xz は 0 と 1 の個数が異なる文字列 - xz L eq より矛盾 4-4 / / / 27

xy p m z = xyz + y p m 1 = p + m(p m 1) = (1 + m)(p m) - p n + 2 と m xy n より p m (n + 2) n 2 よって w は素数でないので矛盾 L,M を正規言語とするとき以下の言語は正規言語 - 和集合 :L M 積集合 :L M - 補集合 :L 差集合 :L M - 反転 :L R = {w R w L} -

2 例 : を利用して L rev = {uu R u {0, 1} } が正規言語でないことを示す - L rev が正規言語と仮定 - で定まる n から w = 0 n 110 n L rev を決める - y ε, xy n, k 0, xy k z L rev を満たす分割 - y = 0 m (0 < m) より xz = 0 l 110 n (l < n) - xz L rev より矛盾例 : を利用して L pr ( 素数個の 1 の文字列からなる言語 ) が正規言語でないことを示す - L pr が正規言語と仮定で n が定まる - p を p n + 2 なる素数とする w = 1 p とする - y ε, xy n, k 0, xy k z L pr を満たす分割 - y = m(m 1) w = xy p m z とおく - w L pr また w = xy p m z = xyz + y p m 1 = p + m(p m 1) = (1 + m)(p m) - p n + 2 と m xy n より p m (n + 2) n 2 よって w は素数でないので矛盾 L,M を正規言語とするとき以下の言語は正規言語 - 和集合 :L M 積集合 :L M - 補集合 :L 差集合 :L M - 反転 :L R = {w R w L} - スター閉包 :L 連接 :L.M - 準同型の像 : h(l) = {h(w) w L, h は } - 準同型の逆像 : h 1 (L) = {w h(w) L, h は } 4-7 / / / 27 例 :(0 + 1) 01 を認識する DFA 定理 4.4:M と M が正規言語ならば M M も正規言語証明 :M,M をそれぞれ表す正規表現 R,R が存在するこのとき M M = L(R+R ) 定理 4.8:L と M が正規言語ならば L M も正規言語証明 1: ドモルガンの法則より L M = L M 正規言語は和集合と補集合で閉じていることから L M も正規言語定理 4.5:M が Σ 上の正規言語ならば M = Σ M も正規言語証明 :M を認識する DFA A = (Q, Σ, δ, q 0, F) が存在するこのとき A = (Q, Σ, δ, q 0, Q F) は M を認識する例 :(0 + 1) 01 の補集合を認識する DFA 直積を用いて直接 L M を認識するオートマトンを作成することも出来る直接の方が作成の手間がかからない 4-10 / 27 問 :(0 + 1) 01 の補集合を表す正規表現は? 4-11 / / 27

に関する帰納法により次が証明できる δ((q L, q M ), w) = (δ L (q L, w), δ M (q M, w)) - これより L(A) = L(A L ) L(A M ) が証明される 4-13 / 27 4-14 / 27 4-15 / 27 例 :(c) は (a) (b) 定理 4.

3 定理 4.8:L と M が正規言語ならば L M も正規言語証明 2:L,M を認識するオートマトンを A L = (Q L, Σ, δ L, q L, F L ) A M = (Q M, Σ, δ M, q M, F M ) とするこれらは ( 簡単のために )DFA とする - A L と A M を同時に模倣するオートマトン A を構成する証明 2 ( 続き ) - a を読み込んだとき A L で状態 p から s へ A M で状態 q から t へ遷移する場合 A で状態 (p, q) から (s, t) へ遷移するように構成する証明 2( 続き ) - 形式的には A = (Q L Q M, Σ, δ, (q L, q M ), F L F M ) ここで δ((p, q), a) = (δ L (p, a), δ M (q, a)) - w に関する帰納法により次が証明できる δ((q L, q M ), w) = (δ L (q L, w), δ M (q M, w)) - これより L(A) = L(A L ) L(A M ) が証明される 4-13 / / / 27 例 :(c) は (a) (b) 定理 4.10:M,M が正規言語ならば M M も正規言語証明 :M M = M M なので定理 4.5 定理 4.8 より明らか定理 4.11:M が正規言語ならば M R も正規言語証明 1:M を認識するオートマトン A から M R を認識するオートマトン A を構成する - A の受理状態を一つに変更する ( 新しい受理状態 q f を導入し旧受理状態から q f へ ε 遷移を作る ) - 矢印をすべて逆向きにして受理状態と初期状態を入れ換えて A を構成する定理 4.11:M が正規言語ならば M R も正規言語証明 2: 正規表現 E を反転した言語を表す正規表現 E R を帰納的に与える基底 : ε R =ε R = a R =a 帰納 : - (F+G) R =F R +G R - (F.G) R =G R.F R - (F ) R =(F R ) このとき L(E R ) = (L(E)) R が E の構成に関する帰納法で証明できる 4-16 / / / 27

4 以下の性質を満たす関数 h : Σ Σ を Σ 上の (homomorphism) という h(a 1 a 2 a n ) = h(a 1 )h(a 2 ) h(a n ) h による言語 L の像 : h(l) = {h(w) w L} 例 :h(0) = ab, h(1) = ε で定まる h : {0, 1} {a, b} を考えるとき - h(0011) = ababεε = abab - h(l(10 1)) = h({11, 101,...}) = {ε, ab,...} = L((ab) ) h から定まる正規表現の変換 ĥ の定義 : 基底 : ĥ(ε) = ε ĥ( ) = ĥ(a) = h(a) 帰納 : - ĥ(f+g) = ĥ(f )+ĥ(g) - ĥ(f.g) = ĥ(f ).ĥ(g) - ĥ(f ) = ĥ(f ) 例 :ĥ(10 1) = ε(ab) ε = (ab) 定理 4.14:M が正規言語ならばそのによる像 h(m) も正規言語証明 :M を表す正規表現を E とし L(ĥ(E)) = h(l(e)) を E の構成に関する帰納法で示す - 基底 :E = ε または E = のとき ĥ(e) = E より L(ĥ(E)) = L(E) = h(l(e)) - E = a h(a) = b 1 b n のとき L(ĥ(a)) = L(b 1 b n ) = {b 1 b n } = h({a}) = h(l(a)) 4-19 / / / 27 証明 ( 続き ): - 帰納 :E = F+G のとき L(ĥ(F+G)) = L(ĥ(F)+ĥ(G)) = L(ĥ(F)) L(ĥ(G)) = IH h(l(f )) h(l(g)) = h(l(f) L(G)) = h(l(f +G)) - E = F.G のとき L(ĥ(F.G)) = L(ĥ(F).ĥ(G)) = L(ĥ(F))L(ĥ(G)) = IH h(l(f))h(l(g)) = h(l(f)l(g)) = h(l(f.g)) - E = F のとき L(ĥ(F )) = L(ĥ(F) ) = L(ĥ(F)) IH = h(l(f )) = h(l(f) ) = h(l(f )) 4-22 / 27 h : Σ Σ による言語 L Σ の逆像 h 1 (L) = {w Σ h(w) L} 4-23 / 27 例 :h(a) = 01, h(b) = 10 で定まる h : {a, b} {0, 1} を考える L 001 = L((00 + 1) ) L ba = L((ba) ) とするとき h 1 (L 001 ) = L ba の証明 :w = (ba) n (0 n) とする h((ba) n ) = (1001) n L 001 より w = (ba) n h 1 (L 001 ) の証明 : 対偶を示す w L ba とする - w が a で始まるとき h(w) は 01 で始まるので - w が b で終るとき h(w) は 10 で終るので - w が aa を含むとき h(w) は 0101 を含むので - w が bb を含むとき h(w) は 1010 を含むのでよって w h 1 (L 001 )) = L ba 4-24 / 27

5 定理 4.16: h : Σ Σ による正規言語 L Σ の逆像は正規言語証明 :L を認識する DFA A = (Q, Σ, δ, q 0, F ) から DFA B = (Q, Σ, γ, q 0, F) を構成するここで γ(q, a) = δ(q, h(a)) このとき γ(q 0, w) = δ(q 0, h(w)) ( w に関する帰納法で証明 ) これより h 1 (L) = L(B) が導ける例 :h(a) = 01,h(b) = 10 のとき DFA A から h 1 (L(A)) = L(B) をみたす DFA B を構成する 1 0 0, 1 q 0 q 1 1 q 2 0 DFA A a b b q 0 q 1 q 2 a DFA B a, b 正規言語に関する決定可能な問題空問題 (L =?) 所属性判定 (w L?) 等価性判定 (L(A) = L(A )?) 4-25 / / / 27

オートマトン形式言語及び演習 3. 正規表現酒井正彦正規表現とは正規表現 ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械正規表現 : 言語

オートマトン形式言語及び演習 3. 正規表現酒井正彦正規表現とは正規表現 ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械正規表現 : 言語オートマトン形式言語及び演習 3. 酒井正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ とは ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械 : 言語を記号列で定義 - 記述しやすい ( ユーザフレンドリ ) 例 :01 + 10 - UNIX の grep コマンド - UNIX の

オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 正規言語の性質 反復補題正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると

オートマトン形式言語及び演習 4. 正規言語の性質酒井正彦正規言語の性質反復補題正規言語が満たす性質ある与えられた言語が正規言語でないことを証明するためにその言語が正規言語であると