オートマトン 形式言語及び演習 1 有限オートマトンとは 酒井正彦 wwwtrscssinagoya-uacjp/~sakai/lecture/automata/ 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, } 形式言語 : 数学モデルに基づいて定義された言語 認識機械 : 文字列が該当言語に属するか? 文字列 機械 受理 / 非受理 文法 : 規則により該当言語に属する文字列を生成規則の例 :S 11S 0 生成の例 :S 11S 1111S 11110 言語のクラス 言語を定義する数学モデル ( 上の方がクラスが広い ) 言語の名称文法認識機械 帰納的可算 ( 制限なし ) チューリング機械 文脈自由 文脈自由 プッシュダウン オートマトン 正規 正規 有限オートマトン 1-1 / 27 1-2 / 27 1-3 / 27 有限オートマトン 有限オートマトン 状態をもつシステムに応用 - ディジタル回路の動作設計 - コンパイラの字句解析 - WEBなどのテキストからのキーワード検索 - 通信プロトコルなどの有限状態システムの検査 例 : オン オフ切り替えスイッチ 例 : 文字列 then の認識 アルファベット : 記号の空でない有限集合 - 例 :Σ = {0, 1} 2 進アルファベット - 例 :Σ = {a, b,, z} すべての小文字の集合文字列 : アルファベット中の記号の有限列 - 例えば 01101 空列 :0 個の記号からなる文字列 - ε で表す 1-4 / 27 1-5 / 27 1-6 / 27
列の長さ : 記号の出現の数 - w の長さを w で表す - 例 : 011 = 3 ε = 0 アルファベットのベキ : Σ k は Σ から作られる長さ k の列の集合 - 例 : Σ = {0, 1} Σ 1 = {0, 1} Σ 2 = {00, 01, 10, 11} Σ 0 = {ε} - 質問 :Σ 3 の要素数は? Σ 上の全ての列の集合 Σ : Σ = Σ 0 Σ 1 Σ 2 また Σ + = Σ 1 Σ 2 Σ 3 Σ = Σ + {ε} 連接 : x と y を文字列とするとき xy は x が表す文字列の後に y が表す文字列をつないで得られる文字列を表す x = a 1 a 2 a i y = b 1 b 2 b j xy = a 1 a 2 a i b 1 b 2 b j - 例 : x = 01101 y = 110 xy = 01101110 - 任意の列 x について xε = εx = x が成り立つ 言語 : L Σ のとき L を (Σ 上の ) 言語という 言語の例 : - 英単語の集合 - C プログラムの集合 - いくつかの 0 のあとに同数個の 1 が並んだ列からなる集合 {ε, 01, 0011, 000111, } - 0 と 1 が同じ数だけ含まれている列の集合 {ε, 01, 10, 0011, 01011001, } 1-7 / 27 1-8 / 27 1-9 / 27 言語の例 ( 続き ): - 素数を表す 2 進数の集合 L p = {10, 11, 101, 111, 1011, } - 空集合 - 空列だけからなる集合 {ε} 注意 : = {ε} 注意 : アルファベット Σ は有限集合 ( 言語は無限集合も扱う ) (DFA) は 次の 5 項組 A = (Q, Σ, δ, q 0, F ) - Q: 状態の有限集合 - Σ: 有限のアルファベット ( 入力記号の有限集合 ) - δ: 遷移関数 (q, a) p - q 0 Q: 開始状態 - F Q: 最終状態 ( あるいは 受理状態 ) の集合 例 : L = {x01y x, y {0, 1} } を認識するオートマトン A - A = ({q 0, q 1, q 2 }, {0, 1}, δ, q 0, {q 1 }) - 遷移表 - 遷移図 1-10 / 27 1-11 / 27 1-12 / 27
有限オートマトンが文字列 w = a 1 a 2 a n を受理する : 遷移図に以下を満たすパス ( 経路 ) が存在するとき - 開始状態で始まる - 最終状態で終る - ラベルの列が a 1 a 2 a n 例 : 先の有限オートマトン は 文字列 01101 を受理する 遷移関数 δ( 引数 : 状態と文字 返値 : 状態 ) を δ( 引数 : 状態と文字列 返値 : 状態 ) に拡張 (x Σ, a Σ) 基底 : δ(q, ε) = q 帰納 : δ(q, xa) = δ(δ(q, x), a) 受理の形式な定義 A が w を受理 : δ(q 0, w) F A が認識する言語 : L(A) = {w δ(q 0, w) F} オートマトンで認識できる言語 ( それを認識するオートマトンが存在する言語 ) を正則言語 ( あるいは 正規言語 ) という 例 :0 と 1 の出現がそれぞれ偶数回の文字列を受理する DFA 1-13 / 27 1-14 / 27 1-15 / 27 DFA の性質の例と証明 以下で定義される DFA A は L(A) = {w w が奇数 } を満たす 1 q0 1 q 1 (1) と (2) が共に成り立つことを w の長さに関する帰納法で証明する (1) δ(q 0, w) = q 0 ならば w は偶数 その逆も成立 (2) δ(q 0, w) = q 1 ならば w は奇数 その逆も成立 基底 : w = 0 のとき w = ε より明らか 帰納 : w > 0 のとき w = v1 (v Σ ) と書ける (1) ( 右向きの証明 ) δ(q 0, v1) = q 0 とする このとき δ(q 0, v1) = δ(δ(q 0, v), 1) より δ(q 0, v) = q 1 帰納法の仮定 (2) より v は奇数よって w は偶数 w は偶数とすると v は奇数帰納法の仮定 (2) より δ(q 0, v) = q 1 であるから δ(q 0, v1) = δ(δ(q 0, v), 1) = δ(q 1, 1) = q 0 (2) (1) と同様に示せる DFA の例 例 : 教科書 p58 問 221 1-16 / 27 1-17 / 27 1-18 / 27
DFA の例 前ページの例を表現する DFA 状態を 3 ビット列の後ろに a (accepted) か r (rejected) をつけて表す前回の入力の際に D に落ちれば a それ以外なら r とする 図の開始状態は 000r A B 000r 100r 011r 000a 100r 011r 001a 101r 000a 010r 110r 001a 010a 110r 001a 011r 111r 010a 100r 010r 111r 100a 010r 111r 101r 011r 100a 101a 011r 100a 110r 000a 101a 110a 000a 101a 111r 001a 110a 非非決定性のオートマトンの遷移先は状態の集合 例 :01 で終る系列を受理する非 00101 を入力したときの動作 非 非 (NFA) の定義 A = (Q, Σ, δ, q 0, F ) - Q: 状態の有限集合 - Σ: 有限のアルファベット - δ: 遷移関数 (q, a) {p 1,, p n } - q 0 Q: 開始状態 - F Q: 最終状態 ( あるいは 受理状態 ) の集合 1-19 / 27 1-20 / 27 1-21 / 27 非 非 NFA の性質の例と証明 例 : 先程の NFA ({q 0, q 1, q 2 }, {0, 1}, δ, q 0, {q 2 }) ここで δ は次の遷移関数 遷移関数の拡張 (x Σ, a Σ) - 基底 : δ(q, ε) = {q} - 帰納 : δ(q, xa) = p δ(q,x) δ(p, a) 次の NFA は L = {w01 w Σ } を認識する 例 :δ(q 0, 00101) を計算しよう 定義 A が w を受理する : δ(q 0, w) F A が認識する言語 : L(A) = {w δ(q 0, w) F } 次の三つの性質が任意の w Σ について成り立つことを同時帰納法により証明する (1) q 0 δ(q 0, w) (2) q 1 δ(q 0, w) ならば w は 0 で終り その逆も成立する (3) q 2 δ(q 0, w) ならば w は 01 で終り その逆も成立する 1-22 / 27 1-23 / 27 1-24 / 27
基底 : w = 0 のとき (1) は明らか (2) と (3) は両辺が共に偽となり 成立 帰納 :w = xa のとき (1) δ(q 0, xa) = δ(p, a) 帰納法の仮定 (1) より q 0 δ(q 0, x) よって a が 0 と 1 のいずれの場合も q 0 δ(q 0, a) であることから 成立 帰納 ( 続き ):w = xa のとき (2) ( 右向きの証明 ) q 1 δ(q 0, xa) とするこのとき q 1 δ(p, a) であることから a = 0 a = 0 とする帰納法の仮定 (1) より q 0 δ(q 0, x) これと q 1 δ(q 0, 0) から q 1 δ(q 0, x0) 帰納 ( 続き ):w = xa のとき (3) ( 右向きの証明 ) q 2 δ(q 0, xa) とするこのとき q 2 δ(p, a) であることから p = q 1 かつ a = 1 よって 帰納法の仮定 (2) より x は 0 で終る x が 0 で終り a = 1 とする帰納法の仮定 (2) より q 1 δ(q 0, x) これと q 2 δ(q 1, 1) から q 2 δ(q 0, x1) 1-25 / 27 1-26 / 27 1-27 / 27