オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ 正規言語の性質 正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると仮定してを使い 矛盾を導く 閉包性正規言語を演算により組み合わせて得られる言語が正規言語となる演算について調べる 複雑なオートマトンを構成するツールとして利用可能 状態数の減少技術実現するチップ面積の減少 の直観的説明 言語 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-2 / 27 4-3 / 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 4-5 / 27 4-6 / 27
例 : を利用して 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 4-8 / 27 4-9 / 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 4-12 / 27
定理 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 4-14 / 27 4-15 / 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-17 / 27 4-18 / 27
以下の性質を満たす関数 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 4-20 / 27 4-21 / 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
定理 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 4-26 / 27 4-27 / 27