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