オートマトン形式言語及び演習 1. 有限オートマトンとは酒井正彦形式言語言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110,

Size: px

Start display at page:

Download "オートマトン形式言語及び演習 1. 有限オートマトンとは酒井正彦形式言語言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110,"

みずきふしはら
4 years ago
Views:

オートマトン形式言語及び演習 1 有限オートマトンとは酒井正彦 wwwtrscssinagoya-uacjp/~sakai/lecture/automata/ 形式言語言語とは : 文字列の集合例 : 偶数個の 1 の後に 0

文字列機械受理 / 非受理文法 : 規則により該当言語に属する文字列を生成規則の例 :S 11S 0 生成の例 :S 11S 1111S 11110 言語のクラス言語を定義する数学モデル ( 上の方がクラスが広い )

有限オートマトン状態をもつシステムに応用 - ディジタル回路の動作設計 - コンパイラの字句解析 - WEBなどのテキストからのキーワード検索 - 通信プロトコルなどの有限状態システムの検査例 : オンオフ切り替えスイッチ例 :

1 オートマトン形式言語及び演習 1 有限オートマトンとは酒井正彦 wwwtrscssinagoya-uacjp/~sakai/lecture/automata/ 形式言語言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, } 形式言語 : 数学モデルに基づいて定義された言語認識機械 : 文字列が該当言語に属するか? 文字列機械受理 / 非受理文法 : 規則により該当言語に属する文字列を生成規則の例 :S 11S 0 生成の例 :S 11S 1111S 言語のクラス言語を定義する数学モデル ( 上の方がクラスが広い ) 言語の名称文法認識機械帰納的可算 ( 制限なし ) チューリング機械文脈自由文脈自由プッシュダウンオートマトン正規正規有限オートマトン 1-1 / / / 27 有限オートマトン有限オートマトン状態をもつシステムに応用 - ディジタル回路の動作設計 - コンパイラの字句解析 - WEBなどのテキストからのキーワード検索 - 通信プロトコルなどの有限状態システムの検査例 : オンオフ切り替えスイッチ例 : 文字列 then の認識アルファベット : 記号の空でない有限集合 - 例 :Σ = {0, 1} 2 進アルファベット - 例 :Σ = {a, b,, z} すべての小文字の集合文字列 : アルファベット中の記号の有限列 - 例えば空列 :0 個の記号からなる文字列 - ε で表す 1-4 / / / 27

2 列の長さ : 記号の出現の数 - 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 = y = 110 xy = 任意の列 x について xε = εx = x が成り立つ言語 : L Σ のとき L を (Σ 上の ) 言語という言語の例 : - 英単語の集合 - C プログラムの集合 - いくつかの 0 のあとに同数個の 1 が並んだ列からなる集合 {ε, 01, 0011, , } - 0 と 1 が同じ数だけ含まれている列の集合 {ε, 01, 10, 0011, , } 1-7 / / / 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

有限オートマトンが文字列 w = a 1 a 2 a n を受理する : 遷移図に以下を満たすパス ( 経路 ) が存在するとき - 開始状態で始まる - 最終状態で終る - ラベルの列が a 1 a 2 a n 例 : 先の有限オートマトンは文字列 01101 を受理する遷移関数 δ( 引数 : 状態と文字返値

F} オートマトンで認識できる言語 ( それを認識するオートマトンが存在する言語 ) を正則言語 ( あるいは正規言語 ) という例 :0 と 1 の出現がそれぞれ偶数回の文字列を受理する DFA 1-13 / 27 1-14 / 27 1-15 / 27 DFA の性質の例と証明以下で定義される DFA A は

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

3 有限オートマトンが文字列 w = a 1 a 2 a n を受理する : 遷移図に以下を満たすパス ( 経路 ) が存在するとき - 開始状態で始まる - 最終状態で終る - ラベルの列が a 1 a 2 a n 例 : 先の有限オートマトンは文字列を受理する遷移関数 δ( 引数 : 状態と文字返値 : 状態 ) を δ( 引数 : 状態と文字列返値 : 状態 ) に拡張 (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 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 問 / / / 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

Σ, δ, 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,

4 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 で終る系列を受理する非を入力したときの動作非非 (NFA) の定義 A = (Q, Σ, δ, q 0, F ) - Q: 状態の有限集合 - Σ: 有限のアルファベット - δ: 遷移関数 (q, a) {p 1,, p n } - q 0 Q: 開始状態 - F Q: 最終状態 ( あるいは受理状態 ) の集合 1-19 / / / 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

5 基底 : 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

オートマトン形式言語及び演習 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 の

オートマトン 形式言語及び演習 1. 有限オートマトンとは 酒井正彦 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110,

オートマトン形式言語及び演習 1. 有限オートマトンとは酒井正彦形式言語言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110,