数理論理

Transcription

1 オートマトンと計算理論 第 1 部正規表現と有限オートマトン 火曜 5 6 限目必修科目 尾張正樹 居室 :J2415 ( 情報 2 号館 4 階 ) masakiowari@inf.shizuoka.ac.jp 講義資料 : fs.inf.in.shizuoka.ac.jp share class 218 オートマトン

2 本講義の評価について 本講義の成績評価は 課題提出 (web 小テスト ) 期末試験 誤植の指摘と再試験により行います 課題提出 ( メールで連絡します ) を 2 点満点 期末試験を 8 点満点で採点を行います 上記合計 1 点に 誤植の指摘 によるおまけの点数を加えた点が 6 点以上で合格とします

3 再試験は 2 月末から 3 月初旬を予定しています 再試験について 課題提出 + 期末試験 + 誤植の指摘 による評価の結果は 期末試験終了後 比較的早期にお知らせする予定です 課題提出 + 期末試験 + 誤植の指摘 が 6 点に満たなかったが 3 点以上を取った学生には 再試験を受ける機会を与えます 再試験は 1 点満点で採点をし 8 点以上取った場合にのみ単位を与えます

4 誤植の指摘によるおまけの点数 講義資料や期末試験候補問題集には 私の不注意から誤植 ( 書き間違い ) が含まれている可能性があります 講義中に私が気づけなかった誤植を後日メールなどで最初に指摘した学生には 誤植の程度 ( 重要さ ) により ~5 点を与えます 誤植の指摘による点数は 課題提出 + 期末試験 の点数に加算します てにおは の間違いや 漢字の書き間違い などの数学的内容に関係のない間違いは指摘をしても点数にはなりません ( 点加算 ) 数学的内容が異なってしまうような誤植 ( 添え字や変数が間違っているなど ) の場合は 1~5 点の点数を加算します 1 箇所の誤植につき点数をもらえる学生は 1 人のみです 早い者勝ちです 誤植の指摘は メールなどの証拠が残る方法で行い 名前と学籍番号を必ず書いてください

5 期末試験および再試験について (1) 制限時間は約 8 分です 参考書やノート PC などを試験中に見てはいけません 問題は 3~6 題ほど出題されます 問題は 期末試験候補問題集より出題します 問題中の一部のみが出題されたり 複数の問題が 1 題として出題されたりすることもあります 初回講義の時点で 正規表現と有限オートマトン (1-5 回ほど ) に関する候補問題が fs に up されています 残りの候補問題は後日お知らせします

6 期末試験および再試験について (2) 期末試験による成績の評価は 下記の要領で行います 問題 N 題中 M 題正解すれば 8 MM 点とする NN 課題提出(2 点満点 ) を加算して評価とする 再試験による成績の評価は 下記の要領で行います 問題 N 題中 M 題正解すれば 1 MM NN 点とする 1 点満点中 8 点以上取れば 課題提出 + 期末試験 が 6 点未満の場合でも単位を与える

7 課題の提出 (web 小テスト ) について (1) 2-4 回ほど 課題を提出してもらいます 課題提出は 学務情報システム (Livecampus) を用いた web 小テスト形式で行います 課題は講義中に説明しますが 学務情報システムからもメールが送られるようにします 課題提出の締め切りは次の講義の日の前日までとし 1 週間で課題を提出してもらいます

8 課題の提出 (web 小テスト ) について (2) 課題提出による成績の評価は 下記の要領で行います 各回の課題は 1 点満点で採点します N 回課題が提出された場合 II 回目の課題がSS ii 点であったとします この時 以下のようにTTを定義します : TT NN ii=1 SS ii 2 NN 1 このTT (2 点満点 ) と 期末試験の点数 (8 点満点 ) および誤植の指摘による点数を足したものが 最終的な成績になります

9 参考書 メイン : オートマトン 言語と計算理論 岩間一雄 ( コロナ社 ) サブ参考書 : 上記で足りないところの補足用 計算理論の基礎 ( 第 1 2 巻 ) Michael Sipser ( 共立出版 ) アルゴリズムと計算量 谷聖一 ( サイエンス社 SGC ライブラリ 43) 計算理論とオートマトン言語理論 丸山章 ( サイエンス社 ) オートマトン 言語理論 富田悦次 横森貴 ( 森北出版 ) など

10 講義予定 イントロダクション (1 回目 ) 第 1 部正規表現と有限オートマトン 1 章. 形式言語の導入 (1-2 回目 ) 2 章. 正規表現と有限オートマトン (2-5 回目 ) 第 2 部文脈自由文法とプッシュダウンオートマトン 1 章. 文脈自由文法 (5-7 回目 ) 2 章. プッシュダウンオートマトン (7-9 回目 ) 第 3 部チューリング機械と計算理論 1 章. チューリング機械と 型文法 (9-12 回目 ) 2 章. チューリング機械の停止性と決定問題 (12-13 回目 ) 3 章. NP 完全問題 (14-15 回目 )

11 第 部 : イントロダクション この講義で何を学ぶのか?

12 イントロダクション (1) 情報科学科で学んで欲しいこと : 計算機とは何か? Computer= 計算機 この講義の目的 : 計算機とは何か? を数学的に理解する

13 イントロダクション (2) 計算機とは何か? Computer= 計算機 = 計算 (computing) する機械 ( 注意 ) 我々の Computer は 通信 も行っているが この講義では計算のみを扱う ( ネットつながっていない PC)

14 イントロダクション (3) 計算 (computing) って何? 四則演算とその組み合わせ : = 15, 3 9 = 6, 12 1 = 12, 16 3 = 16 3 = ( ) + (4 2) 3 = 42, 微分積分 : dd 2xx2 +4xx 1 dddd xx=1 = 8 1 2xx 2 + 4xx 1 dddd = 5 3 = 線形代数や離散数学の計算も皆さんは知ってます

15 イントロダクション (4) 計算 (computing) って何? 四則演算とその組み合わせ : = 15, ff + : xx 1, xx 2 xx 1 + xx = 6, ff : xx 1, xx 2 xx 1 xx = 12, ff : xx 1, xx 2 xx 1 xx = 16 3 = ff : xx 1, xx 2 xx 1 xx 2 ( ) + (4 2) 3 = 42, gg xx 1, xx 2, xx 3, xx 4 ff ff + ff ff + xx 1, xx 2, xx 3, ff xx 3, xx 1, xx 4

16 イントロダクション (5) 計算 (computing) って何? 微分積分 : dd 2xx 2 + 4xx 1 dddd xx=1 = 8 1 gg xx, aa, bb, cc = aaxx 2 + bbbb + cc に対して 導関数を計算 :gg xx, aa, bb = 2aaaa + bb = ff + ff 2, ff aa, xx, bb. 2 dd 2xx2 +4xx 1 dddd xx=1 = ff + ff 2, ff 2,1, 4 = 8

17 イントロダクション (6) 計算 (computing) って何? 微分積分 : 1 2xx 2 + 4xx 1 dddd = 5 3 = gg xx, aa, bb, cc = aaxx 2 + bbbb + cc に対して 原始関数を計算 : GG xx, aa, bb, cc = aa 3 xx3 + bb 2 xx2 + cccc = ff + ( ff + ( ff ff aa, 3, ff ff xx, xx, xx, ff ff bb, 2, ff xx, xx ), ff cc, xx )

18 イントロダクション (7) 計算 (computing) って何? 微分積分 : 1 2xx 2 + 4xx 1dddd = 5 3 = xx 2 + 4xx 1 dddd = GG 1,2,4, 1 GG,2,4, 1 = ff + ( ff + ( ff ff 2,3, ff ff 1,1, 1, ff ff 4,2, ff 1,1 ), ff 1,1 ) ff + ( ff + ( ff ff 2,3, ff ff,,, ff ff 4,2, ff, ), ff 1, ) = 5 3 = 5 3 = 1.666

19 イントロダクション (8) 計算 (computing) って何? そもそも 何を 計算するのか? 与えられた入力に対して 関数 ff xx 1, xx 2,, xx nn の値を 計算 する 先ほどの例 : 1 ff xx 1, xx 2,, xx nn を四則演算 ff +, ff, ff, ff で表す ff xx 1, xx 2, xx 3, xx 4 = ff ff + ff ff + xx 1, xx 2, xx 3, ff xx 3, xx 1, xx 4 1 ff +, ff, ff, ff の計算の仕方は知っているので ff xx 1, xx 2,, xx nn の値が計算できる

20 イントロダクション (9) 先ほどの例 : 1 ff xx 1, xx 2,, xx nn を四則演算 ff +, ff, ff, ff で表す 2 ff +, ff, ff, ff の計算の仕方は知っているので ff xx 1, xx 2,, xx nn の値が計算できる 2は昔は そろばん でやっていた ( 最古の 計算機 )

21 イントロダクション (1) 与えられた入力に対して 関数 ff xx 1, xx 2,, xx nn の値を 計算 する ( 論理回路や数理論理より ) 通常の PC の中では ブール関数 ff:,1 nn,1 の値を論理回路を用いて計算している 例 : ff xx 1, xx 2, xx 3, xx 4 = xx 1 xx 2 xx 3 xx 1 xx 4 = ff ff ff xx 1, xx 2, ff xx 3, ff xx 1, ff xx 4 ここで xx 1, xx 2, xx 3, xx 4,1, ff xx, yy xx yy, ff xx xx など

22 イントロダクション (11) 通常の PC の中では ブール関数 ff:,1 nn,1 の値を論理回路を用いて計算している 例 : ff xx 1, xx 2, xx 3, xx 4 = xx 1 xx 2 xx 3 xx 1 xx 4 = ff ff ff xx 1, xx 2, ff xx 3, ff xx 1, ff xx 4 1 ff xx 1, xx 2,, xx nn を論理演算 ff, ff, ff, ff で表す 論理回路を描く ( プログラムを書く ) のと同じ 2 ff, ff, ff, ff の計算をする論理素子が実装されているので ff xx 1, xx 2,, xx nn の値が計算できる

23 イントロダクション (11 ) 複数ビットの出力を持つ関数 ff:,1 nn,1 kk kk 個のブール関数 ff 1,, ff ii,, ff kk ff ii :,1 nn,1 を用いて ff xx 1,, xx nn = ff 1 xx 1,, xx nn,, ff kk xx 1,, xx nn 1 ビット出力のブール関数 ff 1,, ff ii,, ff kk が計算できれば ff は計算できる

24 自然数 N を 2 進数表示すると nn xx 1 xx 2 xx mm と 自然数をビット列で表現できた ( 実際は mmbit では ~2 mm 1 までしか表現できない ) イントロダクション (12) 最初の例 : ff: N N N 論理回路の例 : ff:,1 nn,1 kk

25 イントロダクション (13) 自然数をビット列で表現できた 実際は nnbit では ~2 nn 1 までしか表現できない もっとも 大きな自然数を計算するには 非常に大きな そろばん が必要 メモリの有限性 メモリの制限がなければ いくらでも大きな論理回路を実装可能なはず 全てのビット列の集合を以下で定義 :,1 nn N,1 nn メモリの制限のない ( 架空の )PC は ff:,1,1 を計算

26 イントロダクション (14) 全てのビット列の集合を以下で定義 :,1,1 nn nn N メモリの制限のない ( 架空の )PC は ff:,1,1 を計算 離散数学で 可算集合の可算個の和集合は 可算集合 であることを習った,1 と N は対等 ( 全単射 gg:,1 N が存在 )

27 イントロダクション (15),1 と N は対等 ( 全単射 gg:,1 N が存在 ) 関数 ff: N N は ビット列の写像 gg 1 ff gg:,1,1 に変換できる ビット列の写像 ff:,1,1 関数 gg ff gg 1 : N N に変換できる ( 注意 ) 実際は gg は全単射でなくても 単射であればよく その場合 gg 1 の代わりに 別の単射 gg : N,1 を使う

28 イントロダクション (16) そもそも 通常 自然数 nn N は 1 進法で扱っている 1,2,3, 9, 1,11,12,.99, 1,11.,999, 1 進法では 自然数 nn に,1,, 9 の列 xx 1 xx 2 xx mm を対応させる 全ての,1,, 9 の列の集合を以下で定義 :,1,, 9 nn N,1,, 9 nn,1,, 9 と N も対等 全単射 gg:,1,, 9 N が存在

29 イントロダクション (17),1,, 9 と N も対等 全単射 gg:,1,, 9 N が存在 関数 ff: N N は,1,, 9 の列の写像 gg 1 ff gg:,1,, 9,1,, 9 に変換できる,1,, 9 の列の写像 ff:,1,, 9,1,, 9 関数 gg ff gg 1 : N N に変換できる

30 イントロダクション (18) 任意の自然数 mm に対して mm 進法が存在する (mm 2) 同様の議論により 関数 ff: N N は,1,, mm 1 の列の写像 fff:,1,, mm 1,1,, mm 1 に変換できる,1,, mm 1 nn N,1,, mm 1 nn

31 イントロダクション (19) そもそも アラビア数字を使う必要性はない 任意の記号 ( 文字 ) の集合 ( アルファベット )Σ aa 1,, aa mm は,1,, mm 1 と対等 Σ aa 1,, aa mm の列を以下で定義 : Σ = aa 1,, aa mm nn N aa 1,, aa mm nn Σ と N は対等なので 関数 ff: N N は Σ の列の写像 fff: Σ Σ に変換できる

32 イントロダクション (2) 計算 (computing) って何? そもそも 何を 計算するのか? 答え : 記号の列 Σ の写像 ff: Σ Σ Σ =,1 のときはビット列の写像になる Σ と N は対等な集合なので 自然数の関数 ff: N N を考えているのと同じである

33 イントロダクション (21) 計算 (computing) って何? どのように 計算するのか? 通常 人間 ( 手計算 そろばん ) や PC( 機械 ) は 定式化された手順 ( アルゴリズム ) に従って計算を進めている アルゴリズムは 人間や機械が 精確に順を追って従うことのできる規則のリストとして指定される 人間が計算を行う動作を 単純化していくことで 計算の仕方 を数学的に定義する

34 イントロダクション (22) 人間 (A さん ) が計算を行う動作を 単純化していくことで 計算の仕方 を数学的に定義する A さんは 紙とペンで計算を進めていくとする 左図のように 掛け算を計算する しかし この計算は一列に書いても 本質は失わない = =

35 イントロダクション (23) = = AA さんは マス目が書いてある一次元の非常に長いテープを使って 上記の計算を行うことにする = = AAさんは テープに沿って行ったり来たりしながら 記号を書きくわえたり 書き込まれた記号を消したりして計算を進めていく

36 イントロダクション (24) テープに沿って行ったり来たりしながら 記号を書きくわえたり 書き込まれた記号を消したり AA さんが 次にどの記号を書き込むか は AA さんが注意を向けている記号 と AA さんの心の状態 ( もしくは脳の状態 ) で決まる = =

37 イントロダクション (25) AA さんが 次にどの記号を書き込むか は AA さんが注意を向けている記号 と AA さんの心の状態 ( もしくは脳の状態 ) で決まる ここにAAさんの注意が向けられているとする = 1かける7は7なので Aさんは7を書き込む = 7

38 イントロダクション (26) ここに AA さんの注意が向けられているとする = = 7たすは7なので 7を書き込む 注意を動かす = = 7 7 たす 1 は 8 なので 8 を書き込む ( 先ほどは掛け算だった!) = = 8 7

39 イントロダクション (27) AA さんが掛け算をするのか 足し算をするのかは AA さんの心の状態に依存する 一般に 計算を遂行する人物 ( 機械 ) は 以下の制約の下で作業を行う : 1 計算過程の各段階において 少数の記号だけに注意が向けられる 2 各段階の動作の決定は 注意を向けられている記号と 計算を実行している人物の現在の心の状態だけに依存する

40 イントロダクション (27 ) 1 計算過程の各段階において 少数の記号だけに注意が向けられる どれだけの数の記号に同時に注意を向ける必要があるか? 同時に複数の記号に注意を向ける代わりに 一つずつ順番に それらの記号に注意を向けてもよい また 注意を向ける位置をテープのあるマス目から遠くの別のマス目に移動させることは マス目を一つずつ

41 イントロダクション (28) 1 計算過程の各段階において 少数の記号だけに注意が向けられる 注意を向ける位置の移動について : 注意を向ける位置をテープのあるマス目から遠くの別のマス目に一気に移動させる代わりに マス目を一つずつ移動させても本質的に同じ = = 7

42 イントロダクション (29) = = 7 結局 どのような計算作業も以下の手続きで実行できる : 計算は マス目で区切られた紙テープに記号を書くことで遂行される 計算過程の各ステップで ある 1 つのマス目に書かれた記号に注意を向ける 各ステップでの動作 : 1 注意を向けていたマス目に記号を書き込む ( 上書きする ) 2 注意を向ける位置を 右か左 に 1 マス移動させる この動作 ( 書き込む記号と 右か左 ) は 注意が向けられた記号と AA さんの心の状態で決定される

43 イントロダクション (3) = = 7 A さんを機械で置き換える A さんが注意を向ける記号 情報を読み書きするヘッド A さんの心の状態 機械の内部状態 1 1 ヘッド

44 イントロダクション (31) = = 7 機械 ( チューリング機械 ) は以下のように動作する : 機械は マス目で区切られた紙テープにヘッドを使って記号を読み書きして 計算を進める 計算過程の各ステップで ヘッドはある 1 つのマス目にある 各ステップでの動作 : 1 ヘッドのあるマス目に記号を書き込む ( 上書きする ) 2 ヘッド位置を 右 or 左 に 1 マス移動させる この動作 ( 書き込む記号と 右 or 左 ) は ヘッドの位置にある記号と 機械の内部状態で決定される 写像 δδ:( ヘッド位置の記号, 内部状態 ) ( 書き込む記号 右 or 左 ) が実質的に アルゴリズム になっている

45 イントロダクション (32) = = 7 チャーチ=チューリングのテーゼ (Church-Turing thesis): 現実の計算機で計算できる関数は チューリング機械で計算できる関数である 逆に チューリング機械で計算できる関数は メモリが十分にあれば 現実の計算機で計算できる どのような新しい仕組みの計算機を設計しても その計算機で計算できる関数は チューリング機械で計算可能な関数になるという経験則もしくは予測

46 イントロダクション (33) = = 7 チューリング機械 = 通常の計算機の数学的モデル ( 計算モデル ) 一般に チューリング機械のように 次の動作 が 現在読んでいる記号 と 内部状態 に依存して決定される計算モデルをオートマトンと呼ぶ 通常の計算機より 低い能力 しか持たない より 簡単な仕組 みの計算機のモデルにも興味がある

47 イントロダクション (34) = = 7 チューリング機械より 低い能力 しか持たない より 簡単な仕組 みのオートマトン : 1 1 有限オートマトン : テープは読むことしかできない プッシュダウンオートマトン : テープは読むことしかできない スタックを持つ = 情報の出し入れが先頭からしかできないメモリ ) AA BB BB ヘッド 1 ヘッド

48 イントロダクション (35) 複数ビットの出力を持つ関数 ff:,1 nn,1 kk kk 個のブール関数 ff 1,, ff ii,, ff kk ff ii :,1 nn,1 を用いて ff xx 1,, xx nn = ff 1 xx 1,, xx nn,, ff kk xx 1,, xx nn 1 ビット出力のブール関数 ff 1,, ff ii,, ff kk が計算できれば ff は計算できる よって この講義では 当面の間 1 ビットの出力を持つ関数の計算のみを扱う

49 イントロダクション (36) この講義では 当面の間 1 ビットの出力を持つ関数の計算のみを扱う 1 ビットの出力しか持たないオートマトンのみを扱う 入力の記号列 xx Σ に対してオートマトンが1を出力するとき xxを受理するオートマトンがを出力するとき xxを拒否すると呼ぶ ( オートマトンは永遠に止まらない可能性もある )

50 イントロダクション (37) 1 ビットの出力の関数 ff: Σ,1 は ff xx = 1 となる列の集合 LL xx Σ ff xx = 1 を指定すると完全に決定できる ff は部分集合 LL の定義関数である ff があるオートマトン MM で計算可能 MM は xx LL を受理 xx LL を拒否する

51 イントロダクション (38) 記号集合 ( アルファベット ) Σ を固定したとき 記号の列全体の集合 Σ の部分集合を言語と呼ぶ LL が言語のとき 記号列 xx LL を LL に属する文章と呼ぶ オートマトン MM で言語 LL が認識可能 MM は xx LL を受理 xx LL を拒否する LL の定義関数 ff があるオートマトン MM で計算可能

52 イントロダクション (39) オートマトン MM で言語 LL が認識可能 MM は xx LL を受理 xx LL を拒否する オートマトンのクラス ( チューリング機械 有限オートマトン ) を固定する このクラスに属するあるオートマトンMMで認識可能な言語を このクラスのオートマトンで認識可能な言語と呼ぶ チューリング機械で認識可能な言語の集合 プッシュダウンオートマトンで認識可能な言語の集合 有限オートマトンで認識可能な言語の集合 などを知りたい

53 イントロダクション (4) 与えられた言語 LL を コンパクトに ( 簡潔に ) 指定したい 与えられた文章が日本語 ( 英語 ) であるかどうかは 文章が日本語 ( 英語 ) の文法に従って作られているかどうかで 判断できる 同様に 言語 LL に対して その文法に従って文章 xx が作られているかどうかで LL に入っているかどうかを判断できるもの ( 形式文法 生成文法 ) を定義することができる 形式言語理論

54 イントロダクション (41) 同様に 言語 LL に対して 文章 xx が LL に入っているかどうかを判断する文法 ( 形式文法 生成文法 ) を定義することができる 文法のクラスとオートマトンのクラスの対応 : チューリング機械で認識可能な言語の集合 = 型文法で生成可能な言語の集合プッシュダウンオートマトンで認識可能な言語の集合 = 文脈自由文法で生成可能な言語の集合有限オートマトンで認識可能な言語の集合 = 正規文法 ( 正規表現 ) で生成可能な言語の集合

55 言語のモデルと計算機のモデルの対応を理解する 講義全体の前 3 分の 2 = オートマトンと言語理論 主題は 2 つ オートマトン : 計算機のモデル ( 抽象機械 ) 有限オートマトン プッシュダウンオートマトン チューリング機械 形式言語 : ( プログラミング ) 言語のモデル 正規表現 正規言語 正規文法 文脈自由文法 文脈自由言語 型文法 型言語

56 講義全体の後ろ 3 分の 1 = 計算理論 計算模型やアルゴリズムを理論的に扱う分野 計算可能性理論 与えられた問題がコンピュータで解けるか? チューリング機械の停止性問題 計算複雑性理論時間計算量 : 計算にかかるステップ数空間計算量 : 計算に必要なメモリ量特に計算量クラスNPについて詳しく抗議する

57 第 1 部正規表現と有限オートマトン

58 第 1 章 : 形式言語の導入 1. 文章の意味を理解する 2. 文章の正しさを理解する 3. 形式言語を導入する

59 1. 文章の意味を理解する (1) 計算機に文章の意味を理解させるにはどうしたらよいか? 数式を文章の例にとって考える : (8 + 13) 二つの数の加減乗除しか知らない小学生にこの計算の仕方を教えよう!

60 1. 文章の意味を理解する (2) 木をつかって数式 ( 文章 ) を記述する木 = 連結で 閉路のない 無向グラフ ( 親 ) 根 枝 頂点 ( 子 ) 葉葉葉葉

61 1. 文章の意味を理解する (3) 15 木をつかって する + 根 葉 / 枝 + 51 (8 + 13) を記述 頂点 頂点に演算子を置く 葉に数字を置く

62 1. 文章の意味を理解する (3) 葉から初めて 子から親へ計算をしていく = = 葉 23 / 7 + 根 + + 枝 = 15 頂点 = =

63 1. 文章の意味を理解する (4) 文章 : (8 + 13) 対応する意味 : 木 木があれば 式の値を 簡単に計算できる 導出木と呼ぶ 文章から木を導くルールを文法と呼ぶ

64 2. 文章の正しさを解析する (1) 文章の意味が定まるためには 文章が 正しい 必要がある 正しい文章ってなに? 例 : カッコ文数式から数値や演算子を消しカッコだけ残した ( ( ) ( ( ) ) ( ( ) ) この文章は正しいだろうか?

65 2. 文章の正しさを解析する (2) 例 : カッコ文数式から数値や演算子を消しカッコだけ残した ( ( ) ( ( ) ) ( ( ) ) この文章は正しいだろうか? 答え : 正しくない理由 : 左カッコ ( が右カッコ ) よりも多いから (6 個 ) (5 個 ) 左カッコの数 = 右カッコの数が必要

66 2. 文章の正しさを解析する (3) カッコ文の二つ目の例 : ( ( ) ( ( ( ) ) ) ) ) ( ( ) ( ( ) ) この文章は正しいだろうか?

67 2. 文章の正しさを解析する (3 ) カッコ文の二つ目の例 : ( ( ) ( ( ( ) ) ) ) ) ( ( ) ( ( ) ) この文章は正しいだろうか? 答え : 正しくない ( ( ) ( ( ( ) ) ) ) ) ( ( ) ( ( ) ) 赤いところだけをみると 右カッコ ) が左カッコ ( よりも多い 既出のカッコが全て閉じられているのに 次に右カッコ ) が来ている

68 2. 文章の正しさを解析する (4) 結局 : カッコ文は次の条件を満たすときに 正しい 文全体に対して : 左カッコ ( の数 = 右カッコ ) の数 任意の n に対して 最初から n 文字目までで 左カッコ ( の数 右カッコ ) の数

69 2. 文章の正しさを解析する (4 ) 練習 : カッコ文の正しさを検証するにはどうしたら良いか考えよ ( どのようなプログラムを書けばよいか?) ヒント : スタックを使うと簡単 A A A A

70 2. 文章の正しさを解析する (5) 解答例 : カッコ文を左から読んでいく 左カッコを読む スタックを一つ積む 右カッコを読む スタックを一つ取り出す スタックが空のとき右カッコを読むと 正しくない と判断 最後まで文を読んだとき スタックが空なら正しいと判断 ( ) A ( ) プッシュダウンオートマトンの簡単な例になっている A A ( ) A A A ( ) A A A A

71 3. 形式言語の導入 (1) 形式言語 : ( プログラミング or 人工 ) 言語の ( 数学的 ) モデル 文字 ( もしくは記号 ) 日本語 : ひらがな カタカタ 漢字 形式言語 :,1,a,b,c, などの数字やローマ字 アルファベット 記号の有限集合 例 :,1, {aa, bb, cc} など この授業では アルファベットを Σ ( シグマ ) で通常表す

72 3. 形式言語の導入 (2) アルファベット Σ 上の列 ( もしくは文章もしくは記号列 ) Σ 上の記号を重複を許して一列に並べたもの ある nn N に対して Σ nn Σ Σ の元 例 : Σ =,1 のとき, 1, 1, 1, 111, 1111, などが列 Σ = aa, bb, cc のとき aa, bb, cc, aaaa, bbbb, bbbb,, aaaaaaaaaa, などが列

73 3. 形式言語の導入 (3) 列 xx の長さ xx := 列に含まれる記号の個数 例 : Σ =,1 のとき xx = 111 の長さは xx = 5 Σ = aa, ee, ss のとき xx = ssssss の長さは xx = 3 空列 εε := 長さが の列 よって εε =

74 3. 形式言語の導入 (4) 列 xx の逆 xx RR xx を後ろから順に読んだ列 xx = xx 1 xx 2 xx nn 1 xx nn (xx ii Σ) のとき xx RR = xx nn xx nn 1 xx 2 xx 1 xx = aa (aa Σ) のとき xx = xx RR = aa εε RR εε 例 : xx = 111, yy =, zz = 111 なら xx RR = 111, yy RR =, zz RR = 111

75 3. 形式言語の導入 (5) 列 xx と列 yy の連接 xxxx := 列 xx の後に列 yy をつけた列 例 :xx = 111, yy = なら xxxx = 111 同じ列の連接 : xx 2 : = xxxx, 例 :xx = 1 のとき xx 2 = 11, 空列 εε と任意の列 xx に対して εεεε = xxxx = xx

76 3. 形式言語の導入 (6) 3 つ以上の列の連接 列 xx, yy, zz に対して xxxxxx xxxx zz = xx yyyy xx 3 xx 2 xx = xxxxxx,, xx εε と約束しておく nn xx nn = xx nn 1 xx = xx xx 例 :xx = 1 のとき xx 2 = 11, xx 3 = 111, xx 4 = 1111, 連接は結合則を満たす

77 3. 形式言語の導入 (7) 列 xx の部分列 : 列 xx の一部分の列のこと 列 ww は列 xx の部分列 ある列 yy, zz が存在して xx = yyyyyy 例 xx = 111のとき yy =, zz = 1, ww = 11とすると yy zz wwはすべてxxの部分列である

78 3. 形式言語の導入 (8) アルファベット Σ 上の長さ nn の列の集合 :Σ nn nn Σ nn = Σ Σ Σ εε と定義する アルファベットΣ 上の全ての列の集合 :Σ Σ Σ nn = Σ Σ 1 Σ 2 nn

79 3. 形式言語の導入 (9) アルファベットΣ 上の言語 LL := Σ 上の列の集合つまり Σ の部分集合 (LL Σ ),1 上の言語の例 : 有限集合 :,1,,111 無限集合 : 1 nn nn nn } 1, 11, 111,. という集合 無限集合をいかにして書き表すか が前半の主題 言語の特別な例 : 全ての列の集合 :Σ 例えば,1 εε,,1,,1,1,, 空集合 : どのような列も含まない言語空列集合 εε : 空列 εεのみからなる言語

80 3. 形式言語の導入 (1) 例題 以下はどのような言語であるか推測しなさい LL 1 = 1, 1, 1, 1, 1, LL 2 = {εε,, 11,, 11, 11, 1111,, 11, 11, 1111, } LL 3 = {1, 1, 11, 11, 111, 1, 11, 11, 111, 11, 111, 111, 1111, 11, 111, 111, 1111, 111, 1111, 1111, 11111, 1, 11, }

81 3. 形式言語の導入 (11) 解答例 LL 1 = 1, 1, 1, 1, 1, = nn 1 nn nn } この授業では nn は整数にしか用いないとする LL 2 = {εε,, 11,, 11, 11, 1111,, 11, 11, 1111, } = xxxx xx Σ } LL 3 = {1, 1, 11, 11, 111, 1, 11, 11, 111, 11, 111, 111, 1111, 11, 111, 111, 1111, 111, 1111, 1111, 11111, 1, 11, } = xxxxx xx, yy Σ, xx = yy }

82 3. 形式言語の導入 (12) 例題 1.2 列 xx Σ の逆をより形式的に定義せよ 解答再帰的定義を用いる 逆 xx RR は 以下の (i) と (ii) により再帰的に定義される : (i) εε RR = εε (ii) 列 xx Σ と記号 ( 長さ1の列 )aa Σに対して aaaa RR = xx RR aa 例 : aaaaaa RR に上記の定義を適応する aaaaaa RR = aa bbbb RR = bbbb RR aa = bb cc RR aa = cc RR bbbb = cc εε RR bbbb = εε RR cccccc = εεεεεεεε = cccccc

83 3. 形式言語の導入 (13) 例題 列 xx で xx = xx RR を満たすものを回文と呼ぶ 回文の再帰的定義を与えよ ヒント : 回文を再帰的に作成するルールを考える

84 3. 形式言語の導入 (14) 例題 列 xx で xx = xx RR を満たすものを回文と呼ぶ 回文の再帰的定義を与えよ ( 回文の例 :εε,,11,11,,11, 11 など ) 解答 (i) 空列 εεと長さ1の列 ( 記号 ) は回文である (ii) 回文 wwと記号 xx Σに対して 列 xxxxxxは回文である (i) と (ii) を用いて生成できるものだけが回文である

85 3. 形式言語の導入 (15) 例題 1.3 xx と yy を列としたとき xxxx RR = yy RR xx RR を証明せよ 解答 列 xxxx の長さに関する数学的帰納法で証明する (i) xxxx = のとき xx = yy = εε なので εεεε RR = εε RR = εε = εεεε = εε RR εε RR で正しい

86 3. 形式言語の導入 (16) (ii) xxxx = nn のとき命題が正しいと仮定する xxxx = nn + 1 のときを考える : xx = εε のとき εεεε RR = yy RR = yy RR εε = yy RR εε RR で OK xx εεのとき あるaa Σが存在して xx = aaaaaと書ける xx yyは長さnnなので 帰納法の仮定より xx yy RR = yy RR xx RR よって xxxx RR = aaxx yy RR = aa xx yy RR = xx yy RR aa = yy RR xx RR aa 一方 yy RR xx RR = yy RR aaxx RR = yy RR xx RR aa なので OK (i) (ii) よりすべての nn に対して命題は証明された

87 3. 形式言語の導入 (17) 言語 LL 1 と LL 2 の連接 LL 1 LL 2 LL 1 LL 2 xx 1 xx 2 xx 1 LL 1, xx 2 LL 2 } 例 : LL 1 =,1, LL 2 = {1111,1} のとき LL 1 LL 2 = 1111, 1, 11111, 11 空列のみの言語 {εε}: 任意の言語 LL に対して εε LL = LL εε = LL

88 3. 形式言語の導入 (18) 例題 1.4 任意の言語 LL に対して LLL = LL = を示せ 解答 : LLL = を証明する LL = は同様に証明できる 任意の列 xxに対して xx LL 1 LL 2 xx 1 xx 2 (xx = xx 1 xx 2 and xx 1 LL 1 and xx 2 LL 2 ) である 今 LL 2 = なので xx 2 LL 2 となる xx 2 は存在しない したがって xx = xx 1 xx 2 and xx 1 LL 1 and xx 2 LL 2 を満たす xx 1 と xx 2 の組は存在しない LL 1 LL 2 = LLL に入る xx は存在しない よって LLL は空集合である

89 3. 形式言語の導入 (19) LL 2 = LLLL, LL 3 = LLLLLL, と定義する 一般に LL nn = LLLL nn 1 特別な場合として LL 1 = LL, LL = {εε} と定義する 言語 LLのクリーネ閉包 LL : LL = LL nn = LL LL 1 LL 2 nn のことをスター演算と呼ぶ Σ 上の全ての列の集合 Σ は Σ を長さ 1 の列すべてからなる言語と考えると 言語 Σ のクリーネ閉包になっている

90 3. 形式言語の導入 (2) 例題 1.6 長さが奇数の {,1} 上の列全体からなる言語を表現せよ 解答例 1: 長さが偶数の列全体は,1,1,11 である これに か 1 を一つ加えて :,1,1,11 {,1} 解答例 2: 全ての列の集合から長さが偶数の列の集合を引いて :,1,1,1,11

91 3. 形式言語の導入 (21) 鳩ノ巣原理 : 鳩が nn + 1 羽いて巣箱が nn 個しかないなら 必ず一つの巣箱には 2 羽以上入らなければならない あたりまえのことを言っているように思うが 今後 様々な定理の証明で重要な役割を果たす

92 3. 形式言語の導入 (22) 例題 1.7 nn を 1 以上の整数とし 集合 AA はその大きさが nn + 1 で AA {1,2,, 2nn} を満たすとする このとき AA の元 xx 1, xx 2 で xx 1 が xx 2 を割り切るものが存在することを示せ 解答 :AA = {aa 1, aa 2,, aa nn+1 } とする 各 aa ii を 2 で割れるだけ割って aa ii = 2 bb ii pp ii と書く ここで pp ii は奇数 よって pp ii 1,3,, 2nn 1 集合 1,3,, 2nn 1 の大きさは nn なのに AA の大きさは nn + 1 なので ある pp ii と pp jj (ii jj) は pp ii = pp jj を満たす よって aa ii = 2 bb ii pp ii と aa jj = 2 bb jj pp ii と書ける よって bb ii bb jj なら aa ii が aa jj で bb jj > bb ii なら aa jj が aa ii で割り切れる

93 第 2 章 : 正規表現と有限オートマトン 1. 正規表現 2. 有限オートマトン 3. 非決定性有限オートマトン 4. 有限オートマトンと正規表現の等価性 5. 有限オートマトンの能力の限界

94 1. 正規表現 (1) 言語 ( 列の集合 ) を表現する方法の一つ ( こっちがオリジナル ) アルファベット Σ 上の正規表現 SS および SS が表現する言語 LL(SS) は以下のように再帰的に定義される : 1 は正規表現であり LL =. 2 εε は正規表現であり LL εε = εε. 3 aa Σ なら aa は正規表現であり LL aa = {aa}. 4 RR 1 とRR 2 が正規表現なら RR 1 + RR 2, RR 1 RR 2, (RR 1 ) も正規表現であり LL RR 1 + RR 2 = LL RR 1 LL RR 2, LL RR 1 RR 2 = LL RR 1 LL(RR 2 ), LL RR 1 = LL RR 1 である

95 1. 正規表現 (2) Σ 上の正規表現 SS および SS が表現する言語 LL(SS) の定義 : 1 は正規表現であり LL =. 2 εε は正規表現であり LL εε = εε. 3 aa Σ なら aa は正規表現であり LL aa = {aa}. 4 RR 1 とRR 2 が正規表現なら RR 1 + RR 2, RR 1 RR 2, (RR 1 ) も正規表現であり LL RR 1 + RR 2 = LL RR 1 LL RR 2, LL RR 1 RR 2 = LL RR 1 LL RR 2, LL RR 1 = LL RR 1 である ( 例 ) 1 + : まず は 3 より正規表現. 次に 1 は 4 より正規表現. よって 1 も 4 より正規表現. 最後に 全体が 4 より正規表現になる

96 1. 正規表現 (3) 1 LL =. 2 LL εε = εε. 3 aa Σ なら LL aa = {aa}. 4LL RR 1 + RR 2 = LL RR 1 LL RR 2, LL RR 1 RR 2 = LL RR 1 LL RR 2, LL RR 1 = LL RR 1. 記法の省略 : 1 + を 1 + と書く 連接と + は結合則が成り立つので を と書く RR + RRRR, RR 2 = RRRR,, RR 5 = RRRRRRRRRR, なども用いる

97 1. 正規表現 (4) 1 LL =. 2 LL εε = εε. 3 aa Σ なら LL aa = {aa}. 4LL RR 1 + RR 2 = LL RR 1 LL RR 2, LL RR 1 RR 2 = LL RR 1 LL RR 2, LL RR 1 = LL RR 1. 例題 2.1 次の正規表現はどのような言語を表現しているか : (i) RR 1 = (ii) RR 2 = + εε (iii) RR 3 = ( 解答 ) (i) 正規表現のルール4より LL RR 1 = LL =. = だが = εε, ii = ii 1 より LL RR 1 = = εε (ii) RR = + εε とすると RR 2 = RRRと書ける ルール4と1より LL RR 2 = LL RRR = LL RR LL = LL RR =. (iii) LL + 1 =,1 となり すべての列の集合になる よって LL RR 3 =,1,1 となり どこかに 3 個以上の が連続して現れる,1 上の列の全体となる

98 1. 正規表現 (5) 例題 2.2 RR 4 = cc aa + bbcc はどのような言語を表現しているか ( 解答 ) LL(RR 4 ) は部分列 aaaa を含まない {aa, bb, cc} 上の列全体になる 証明の概略 : LL RR 4 = LL cc aa + bbcc = LL cc LL aa + bbcc = {cc} aa, bb, bbbb, bbbbbb, bbbbbbbb, よって AA = aa, bb, bbbb, bbbbbb, bbbbbbbb, とすると xx LL(RR 4 ) ならば xx = cc jj yy 1 yy 2 yy ii yy nn, yy ii AA cc jj には aaaa は現れない cc jj と yy 1 の境界でも aaaa は現れない yy ii の中では aaaa は現れない 最後に yy ii と yy ii+1 の境界でも現れない よって xx LL(RR 4 ) ならば xx は aaaa を部分列に含まない

99 1. 正規表現 (6) 例題 2.2 RR 4 = cc aa + bbcc はどのような言語を表現しているか ( 解答 ) LL(RR 4 ) は部分列 aaaaを含まない {aa, bb, cc} 上の列全体になる 証明の概略 : 次に xx が aaaa を部分列に含まないならば xx LL(RR 4 ) を証明する xx が aaaa を部分列に含まないと仮定する 列 xx を左から見て行って 記号 cc の前以外 ( つまり aa の前と bb の前 ) と列全体の前と後ろに 切目 を入れる : 例えば xx = cccccc aa aa bbbbbb bb bbbb aa bbbbbbbb bb bb

100 1. 正規表現 (7) xx が aaaa を部分列に含まないと仮定する 列 xx を左から見て行って 記号 cc の前以外 ( つまり aa の前と bb の前 ) と列全体の前と後ろに 切目 を入れる : 今 xx = yy, と書けたとすると 以下の場合が考えられる : (yy の右端が aa の場合 ) aa の左にも切れ目が入り yy = aa (yy の右端が bb の場合 ) bb の左にも切れ目が入り yy = bb (yy の右端が cc の場合 ) この cc から左に見ていくと cc の左には切れ目が入らないし 次がまた cc でも同様 もし cc の左に bb が来るとその左に切目が入る 仮定より cc の左には aa は来ない よって yy = bbcc ii (ii 1) と書ける

101 1. 正規表現 (8) xx が aaaa を部分列に含まないと仮定する 列 xx を左から見て行って 記号 cc の前以外 ( つまり aa の前と bb の前 ) と列全体の前と後ろに 切目 を入れる : xx = yy, と書けたとする いずれの場合も yy AA = aa, bb, bbbb, bbbbbb, bbbbbbbb, なので 結局 xx cc AA = LL(cc aa + bbcc ) となる

102 1. 正規表現 (9) xx,1 にたいして # 1 (xx) を列 xx に含まれる 1 の個数と定義 # (xx) も同様 例題 2.3 LL RR = xx xx,1 かつ # 1 (xx) が偶数 } の正規表現を求めよ ( 解答 ) 例えば xx = LL(RR) は xx = 2 ( )(1 1 )( ) と書ける よって RR = 1 1 が LL(RR) に対応する正規表現

103 1. 正規表現 (1) 例題 : LL 1 : = xx,1 かつ # 1 xx = # xx かつ xx の任意のプレフィックス yy に対して # 1 yy # yy 1} の正規表現を求めよ ただし プレフィックスとは列の先頭から始まる部分列のこと : つまり yy = xx 1 xx 2 と書けるとき xx 1 は yy のプレフィックス ( 解答例 ) xx が から始まるとする # 1 # の次は 1 になる = 2 なので # 1 1 # 1 = なので その次は でも 1 でもよい もし xx = 1 なら 最後の の次は 1 でなければならない 同様に xx = 11 なら 最後の 1 の次は でなければならない 結局 正規表現は と書ける

104 LL 1 を使って LL 2 がどのように書けるかを考えるとよい 例えば xx = は 1LL 1 と書ける 1. 正規表現 (11) 練習問題 : 言語 LL 2 : = xx,1 # 1 xx = # xx かつ xxの任意のプレフィックスyyに対して # 1 yy # yy 2} の正規表現を求めよ ただし プレフィックスとは列の先頭から始まる部分列のこと : つまり yy = xx 1 xx 2 と書けるとき xx 1 は yy のプレフィックス ヒント LL 1 : = xx,1 かつ # 1 xx = # xx かつ xx の任意のプレフィックス yy に対して # 1 yy # yy 1} の正規表現は と書けることを使う

105 1. 正規表現 (12) LL 2 : = xx xx,1 かつ xx の任意のプレフィックス yy に対して # 1 yy # yy 2} LL 1 : = xx xx,1 かつ xx の任意のプレフィックス yy に対して # 1 yy # yy 1} の正規表現は と書ける ( 解答例 ) まず 具体的な例で考える xx: LL 1 # 1 yy # yy : xx: LL 1 LL 1 1LL 1 # 1 yy # yy : xx: LL 1 LL 1 1 # 1 yy # yy : LL 1

106 1. 正規表現 (13) LL 2 : = xx xx,1 かつ xx の任意のプレフィックス yy に対して # 1 yy # yy 2} LL 1 : = xx xx,1 かつ xx の任意のプレフィックス yy に対して # 1 yy # yy 1} の正規表現は と書ける ( 解答例 ) xx: LL 1 LL 1 1LL 1 # 1 yy # yy : xx: LL 1 LL 1 1 # 1 yy # yy : 結局 LL 2 = 1LL 1 + LL 1 1 LL 1 =

107 1. 正規表現 (14) 定理 2.1 言語 LL 1 と LL 2 が正規表現で表現できるなら LL 1 LL 2, LL 1 LL 2, LL 1 もまた正規表現で表現できる ( 証明 ) 正規表現の定義 : 4 RR 1 と RR 2 が正規表現なら RR 1 + RR 2, RR 1 RR 2, (RR 1 ) も正規表現であり LL RR 1 + RR 2 = LL RR 1 LL RR 2, LL RR 1 RR 2 = LL RR 1 LL RR 2, LL RR 1 = LL RR 1 である より定理は自明である

108 問題 以下の正規表現 RRに対して RRが表現する言語 LL RR に含まれる文字列を2つ LL RR に含まれない文字列を2つそれぞれ挙げよ 1 aa bb 2 aa bbbb bb 3 aa + bb 4 aaaaaa 5 aa + bb aa aa + bb bb aa + bb aa aa + bb 6 aaaaaa + bbbbbb 7 εε + aa bb 8 aa + bbbb + bbbb aa + bb

109 問題 以下の言語に対する正規表現を与えよ ただし アルファベットは {,1} とする ( つまり ww,1 ): ww ww は 1 で始まり で終わる ww ww は少なくとも三つの 1 を含む ww ww は部分列 11 含む 4 ww 3 ww かつ ww の 3 番目の文字が 5 ww ww は で始まり長さが奇数 もしくは 1 で始まり長さが偶数 } 6 ww ww は部分列 11 を含まない } 7 ww ww 5

110 問題 ( 前ページの続き ) 8 ww ww 11 かつ ww ww wwの全ての奇数番目は1 1 ww # 1 ww 2 かつ # ww 1 11, εε 12 ww # ww が偶数 もしくは # 1 ww = 2} ww ww εε 15 ww ww が偶数 もしくは ww が3の倍数 }

111 2. 有限オートマトン (1) 正規表現 言語に属する列を 生成 する 有限オートマトン 与えられた列が言語に属するかどうかを 判定する機械 ただし あくまでも イメージ で オートマトンは言語を表現するための 数学的手段 である

112 2. 有限オートマトン (1-1) 有限オートマトン = メモリ容量が著しく制限された計算機のモデル 例 ) 一方通行の自動ドアの制御部 フロントパッド リアパッド ドア

113 2. 有限オートマトン (1-1) 有限オートマトン = メモリ容量が著しく制限された計算機のモデル 例 ) 一方通行の自動ドアの制御部 フロントパッド リアパッド ドア

114 2. 有限オートマトン (1-1) 有限オートマトン = メモリ容量が著しく制限された計算機のモデル 例 ) 一方通行の自動ドアの制御部 フロントパッド リアパッド ドア

115 2. 有限オートマトン (1-1) 有限オートマトン = メモリ容量が著しく制限された計算機のモデル 例 ) 一方通行の自動ドアの制御部 フロントパッド リアパッド ドア

116 2. 有限オートマトン (1-1) 有限オートマトン = メモリ容量が著しく制限された計算機のモデル 例 ) 一方通行の自動ドアの制御部 フロントパッド リアパッド ドア

117 2. 有限オートマトン (1-2) 例 ) 一方通行の自動ドアの制御部 制御部の状態 : OPEN か CLOSED フロントパッド リアパッド ドア

118 2. 有限オートマトン (1-3) 例 ) 一方通行の自動ドアの制御部 制御部の状態 : OPEN か CLOSED フロントパッド リアパッド 入力 : FRONT : 人がフロントパッドにだけいる ドア CLOSED なら OPEN になる OPEN なら OPEN のまま

119 2. 有限オートマトン (1-4) 例 ) 一方通行自動ドアの制御部 制御部の状態 : OPEN か CLOSED フロントパッド リアパッド 入力 : REAR : 人がリアパッドにだけいる ドア フロントからリアへ移動中なら OPEN なので OPEN のまま 逆に CLOSED なら リアからフロントに移動しようとしているので CLOSED のまま

120 2. 有限オートマトン (1-5) 例 ) 一方通行自動ドアの制御部 制御部の状態 : OPEN か CLOSED 入力 : BOTH : 人がフロントとリアの両パッドにいる OPEN なら OPEN のまま CLOSED なら OPEN にする

121 2. 有限オートマトン (1-6) 例 ) 一方通行自動ドアの制御部 制御部の状態 : OPEN か CLOSED フロントパッド リアパッド 入力 : NEITHER : どちらのパッドにも人はいない ドア OPEN なら CLOSED にする CLOSED なら CLOSED のまま

122 2. 有限オートマトン (1-7) 例 ) 自動ドアの制御部 制御部の状態 : OPEN か CLOSED フロントパッド リアパッド 入力 : FRONT : 人がフロントパッドにだけいる REAR : 人がリアパッドにだけいる BOTH : 人がフロントとリアの両パッドにいる NEITHER : どちらのパッドにも人はいない ドア

123 2. 有限オートマトン (1-8) 自動ドアの制御部の状態遷移図 : FRONT REAR BOTH NEITHER NEITHER REAR OPEN FRONT, BOTH CLOSED

124 2. 有限オートマトン (1-9) 自動ドアの制御部の状態遷移図 : 入力 : REAR : OPENならOPENのまま CLOSEDならCLOSEDのまま FRONT REAR BOTH NEITHER NEITHER REAR OPEN FRONT, BOTH CLOSED

125 2. 有限オートマトン (1-1) 自動ドアの制御部の状態遷移図 : 入力 : BOTH : OPEN なら OPEN のまま CLOSED なら OPEN にする FRONT REAR BOTH NEITHER NEITHER REAR OPEN FRONT, BOTH CLOSED

126 2. 有限オートマトン (1-11) 入力を頭文字のみ残して消す FRONT REAR BOTH NEITHER NEITHER REAR OPEN FRONT, BOTH CLOSED

127 2. 有限オートマトン (1-12) 4 つの記号 {F,R,B,N} を入力として受け取って状態を変える機械 今の状態と入力で 次の状態が決まる 有限オートマトン F,R,B N,R OPEN N F, B CLOSED

128 2. 有限オートマトン (1-13) 最後の状態を出力と考える 初期状態 :CLOSED 入力列 : F B R N N R B 出力 :OPEN

129 2. 有限オートマトン (1-14) 初期状態 :CLOSED 入力列 : F B R N N R B 出力 :OPEN 出力が OPEN である入力列が 受理される と考える 受理される 列の集合を言語 LL とする : e.g. FBRNNRB LL LL はこのオートマトンで認識される言語と呼ばれる

130 2. 有限オートマトン (2) 有限オートマトンの概念図 1 1 ヘッド テープ 有限制動部 テープと有限制動部からなる ヘッドがテープを左から右にスキャンする テープはマス目に分かれていて 各マスには記号が書いてあるつまり テープ全体で 列 になっている テープをスキャンした後で 列が言語に属しているかどうかを判定する

131 2. 有限オートマトン (3) 1 1 ヘッド テープ 有限制動部 定義 : 有限オートマトン (fa) は MM = KK, Σ, δδ, ss, FF で与えられる KK, Σ, FF は有限集合 KK : 状態の集合 ( 有限制動部の状態 ) Σ : 入力記号の集合 ( テープに書かれている記号 ) FF KK : 受理状態の集合 ( 状態が FF で止まると入力を受理 ) ss KK : 初期状態 ( 状態は最初 ss である ) δδ :KK Σ KK 状態遷移関数 (ss = δδ ss, aa なら 状態 ss で記号 aa を読むと状態は sss に変わる )

132 2. 有限オートマトン (4) 定義 : 有限オートマトン (fa) はMM = KK, Σ, δδ, ss, FF で与えられる KK : 状態の集合 Σ : 入力記号の集合 FF KK : 受理状態の集合 ss KK : 初期状態 δδ :KK Σ KK 状態遷移関数 ( 例 ) KK = OPEN, CLOSED, Σ = F, R, B, N, FF = {OPEN} 初期状態 ss = CLOSED δδ OPEN, F = OPEN, δδ OPEN, N = CLOSED, δδ CLOSED, F = OPEN, δδ CLOSED, N = CLOSED, etc

133 2. 有限オートマトン (5) 定義 : 有限オートマトン (fa) はMM = KK, Σ, δδ, ss, FF で与えられる KK : 状態の集合 Σ : 入力記号の集合 FF KK : 受理状態の集合 ss KK : 初期状態 δδ :KK Σ KK 状態遷移関数 ( 例 ) KK = ss, ss 1, ss 2, ss 3, Σ =,1, FF = {ss } ss ss 1 ss ss 3 状態遷移図 状態は丸で示す 初期状態を で示す 1 受理状態は二重丸 状態遷移は矢の形で示す e. g. δδ ss, = ss 1, δδ ss, 1 = ss 2

134 2. 有限オートマトン (6) 11 をこの順で読むと ss ss 2 ss ss 1 となる 写像 δδ を δδ ss, 11 = ss 1 となるように ( 再帰的 ) 定義をする : 定義 ( δδ: KK ΣΣ KK) ss KK, aa ΣΣ, xx ΣΣ に対して δδ ss, εε = ss かつ δδ ss, xxxx = δδ δδ ss, xx, aa

135 2. 有限オートマトン (7) 定義 ( δδ: KK ΣΣ KK) ss KK, aa ΣΣ, xx ΣΣ に対して δδ ss, εε = ss かつ δδ ss, xxxx = δδ δδ ss, xx, aa ( 例 ) 11 をこの順で読むと ss ss 2 ss ss 1 δδ ss, εε = ss, δδ ss, 1 = δδ ss, εε1 = δδ δδ ss, εε, 1 = δδ ss, 1 = ss 2, δδ ss, 11 = δδ δδ ss, 1, 1 = δδ ss 2, 1 = ss δδ ss, 11 = δδ δδ ss, 11, = δδ ss, = ss 1

136 2. 有限オートマトン (8) 定義 ( δδ: KK ΣΣ KK) ss KK, aa ΣΣ, xx ΣΣ に対して δδ ss, εε = ss かつ δδ ss, xxxx = δδ δδ ss, xx, aa 記号 aa Σ に対して δδ ss, aa = δδ(ss, aa) なので ハット ^ を省略しても混乱が生じない 結局 δδ の定義域が KK Σ から KK Σ に自然に拡張された 定義 fa MM = KK, ΣΣ, δδ, ss, FF と xx Σ に対して δδ ss, xx FF のとき xx は MM に受理されると呼ぶ MM が受理する列の全体を MM が認識する言語と呼ぶ

137 2. 有限オートマトン (9) fa MM 1 の状態遷移図 例題 2.4 MM 1 の認識する言語を求めよ ( 解答 ) ss ss 1 の個数と 1 の個数がともに偶数となる {,1} 上の列となる 列 xx,1 に対し δδ ss, xx = ss とすると ss = ss であるなら # xx と # 1 xx はともに偶数 ss = ss 1 なら # xx が奇数 # 1 xx は偶数 ss = ss 2 なら # xx が偶数 # 1 xx が奇数 ss = ss 3 なら # xx と # 1 xx はともに奇数 であることを証明する 1 1 ss 2 1 ss 3 1

138 2. 有限オートマトン (1) 列 xx,1 に対し δδ ss, xx = ss とすると ss = ss であるなら # xx と # 1 xx はともに偶数 ss = ss 1 なら # xx が奇数 # 1 xx は偶数 ss = ss 2 なら # xx が偶数 # 1 xx が奇数 ss = ss 3 なら # xx と # 1 xx はともに奇数 ( 証明 ) i) 列 xx の長さが のとき 定義より δδ ss, εε = ss となり OK ii) 列 xx の長さが nn のとき成立していると仮定する 長さ nn + 1 の列 yy は yy = xxxx と書ける # xx が偶数 # 1 xx が奇数で aa = のときを考える 仮定より xx を読み終わった後の状態は ss 2. 状態遷移図より aa = を読むと ss 2 ss 3 となる yy は # xx と # 1 xx がともに奇数なので OK 他もすべて調べると証明が終わる ( 以下省略 )

139 2. 有限オートマトン (11) 例題言語 LL 1 : = xx xx,1 かつ xx の任意のプレフィックス yy に対して # 1 yy # yy 2} を認識する fa を与えよ 解答 : tt 1 1 tt 1 tt 2 1 tt 3,1 tt 3 に行くとかえって来れない

140 2. 有限オートマトン (12) 例題 言語 LL 2 : = xx xx aa, bb, cc かつ xx は部分列 aaaa を含まない } を認識する fa を与えよ 解答 bb, cc aa aa, bb, cc ss aa bb cc ss 1 ss 2 ss 1 は 直前に aa を読んだことを記憶するための状態 ss と ss 1 で aa を読むと ss 1 に行く その次に cc を読むと ss 2 に行き受理されなくなる

141 問題 以下の言語に認識するdfaの状態遷移図を書け ただし アルファベットは {,1} とする ( つまりww,1 ): 1 ww wwは1で始まりで終わる 2 ww wwは少なくとも三つの1を含む 3 ww wwは部分列 11を含む 4 ww 3 ww かつ wwの3 番目の文字が 5 ww wwは で始まり長さが奇数 もしくは 1で始まり長さが偶数 } 6 ww wwは部分列 11を含まない } 7 ww ww 5

142 問題 ( 前ページの続き ) 8 ww ww 11 かつ ww ww wwの全ての奇数番目は1 1 ww # 1 ww 2 かつ # ww 1 11, εε 12 ww # ww が偶数 もしくは # 1 ww = 2} ww ww εε 15 ww ww が偶数 もしくは ww が3の倍数 }

143 2. 有限オートマトン (13) 直積オートマトン ( 直積 fa) 入力アルファベットが等しい二つの fa MM 1 = KK 1, Σ, δδ 1, ss 1, FF 1 と MM 2 = KK 2, Σ, δδ 2, ss 2, FF 2 に対して 状態 : ss 1, ss 2 KK 1 KK 2 状態遷移関数 :δδ ss 1, ss 2, aa δδ 1 ss 1, aa, δδ 2 ss 2, aa 直積オートマトンの初期状態と受理状態は 利用目的によって異なったものを指定する

144 2. 有限オートマトン (14) 定理 2.2 言語 LL 1 と LL 2 が fa で認識できるなら LL 1 LL 2 も fa で認識できる 証明 LL 1 と LL 2 を認識する fa をそれぞれ MM 1 = KK 1, Σ, δδ 1, ss 1, FF 1 とMM 2 = KK 2, Σ, δδ 2, ss 2, FF 2 とする それらの直積 faを以下の初期状態と受理状態集合で作る : 初期状態 : ss 1, ss 2 受理状態集合 : FF ss 1, ss 2 ss 1 FF 1, ss 2 FF 2 xx LL 1 LL 2 なら δδ 1 ss 1, xx FF 1 かつ δδ 2 ss 2, xx FF 2. δδ ss 1, ss 2, xx = δδ 1 ss 1, xx, δδ 2 ss 2, xx FF 直積オートマトンは xx を受理

145 2. 有限オートマトン (15) xx LL 1 LL 2 なら δδ 1 ss 1, xx FF 1 もしくは δδ 2 ss 2, xx FF 2. δδ ss 1, ss 2, xx = δδ 1 ss 1, xx, δδ 2 ss 2, xx FF 直積オートマトンは xx を受理しない よって 直積オートマトンは LL 1 LL 2 を認識する

146 2. 有限オートマトン (16) 直積オートマトンの例 : 以前の2つのオートマトン ss ss ss 2 1 ss 3 1 と で表現される言語 LL 1 とLL 2 に対して LL 1 LL 2 を認識するオートマトンを直積オートマトンで与える : 状態の数は ss, tt,, (ss 3, tt 3 ) の 16 個初期状態は (ss, tt ) 受理状態は ss, tt, ss, tt 1, (ss, tt 2 )

147 2. 有限オートマトン (17) ss, tt 3 ss 1, tt 3 ss 2, tt ss, t ss 2, tt 1 ss, tt 2 ss 3, tt ss 3, tt 3 ss, tt ss1, tt 1 ss 1, tt 1 ss 3, tt ss 2, tt 2 1 ss 3, tt ss 2, tt 1 ss 1, tt 2 1

148 2. 有限オートマトン (18) fa の記憶容量 = 状態の個数 同じ言語を認識する限り より状態の少ない fa が効率の良い fa. 初期状態から到達できない状態は排除しても認識する言語は変わらない ( 冗長な状態 ) 先ほどの直積オートマトンの例では (ss, tt 1 ) は初期状態から到達できないので 削除しても認識する言語は変わらない

149 2. 有限オートマトン (19) 練習問題 : (ss, tt 1 ) 以外にも 初期状態から到達できない状態が 5 つ存在するので探してみよ

150 2. 有限オートマトン (2) 解答例 ss, tt 3 ss 1, tt 3 ss 2, tt ss, t ss 2, tt 1 ss, tt 2 ss 3, tt ss 3, tt 3 ss, tt ss1, tt 1 ss 1, tt 1 ss 3, tt ss 2, tt ss 3, tt ss 2, tt 1 ss 1, tt 2 1

151 2. 有限オートマトン (21) ss, tt 3 ss 1, tt ss 2, tt 3 1 ss, t ss 2, tt 1 ss, tt 2 1 ss 3, tt ss 3, tt 1 1 ss 1, tt 1 ss 3, tt 2 状態を 6 つ削除したオートマトン削除前の直積オートマトンと同じ言語を認識する 1 1

152 2. 有限オートマトン (22) 今後 fa は初期状態から到達できない状態は含まないと仮定する しかし それでもなお冗長な状態が存在する可能性がある 定義 ( 状態の等価性 ) fa MM = KK, Σ, δδ, ss, FF の二つの状態 ss 1 と ss 2 は 全ての列 xx Σ に対して δδ ss 1, xx FF δδ ss 2, xx FF を満たすとき等価であるという

153 2. 有限オートマトン (23) 定理 2.3 (i) fa MM が等価な 2 個の状態を有するならば MM と同じ言語を認識して状態数が MM より 1 個少ない fa MMM が存在する (ii) fa MM には 初期状態から到達できない状態は存在しないとする このとき MM と同じ言語を認識して状態数がより少ない fa MMM が存在するならば MM には ( 少なくとも )2 個の等価な状態が存在する

154 2. 有限オートマトン (24) (i) fa MM が等価な 2 個の状態を有するならば MM と同じ言語を認識して状態数が MM より 1 個少ない fa MMM が存在する ( 証明の概要 ) ss 1 と ss 2 が等価だとする 状態 s から ss 2 への遷移が存在するなら それらを全て ss から ss 1 への遷移に変更する すると ss 2 への遷移がなくなるので ss 2 を削除した fa を MMM とすると MMM は MM より状態が一つ少ない MM と MMM の等価性も証明できる sss ssss sssss sss ssss sssss ss 2 ss 1 ss 2 ss 1

155 2. 有限オートマトン (25) (ii) fa MM には 初期状態から到達できない状態は存在しないとする このとき MM と同じ言語を認識して状態数がより少ない fa MMM が存在するならば MM には必ず 2 個の等価な状態が存在する 証明は複雑なので省略する ( 知りたい人は参考書 )

156 2. 有限オートマトン (26) 定理 2.4 Σ 上の言語 LL が fa で認識できるなら LL の補集合 Σ LL も fa で認識できる ( 証明 ) LL を受理する fa を MM とする MM が受理しない列 を受理する fa を作りたい MM が列 xx を受理しない 列 xx を読み終わると非受理状態にある よって MM の受理状態と非受理状態を入れ替えた fa を MMM とすると MMM は Σ LL を認識する

157 問題 以下の言語に認識する dfa の状態遷移図を書け ただし アルファベットは {aa, bb} とする (ww aa, bb ) 1 ww # aa ww 3, かつ, # bb ww 2 2 ww # aa ww = 2, かつ, # bb ww 2 3 ww # aa ww は偶数, かつ, # bb ww 1,2 4 {ww # aa ww は偶数, かつ, 各々の aa は bb の直後にある } 1 ww ww は aa で始まり, かつ, # bb ww 1} 2 ww # aa ww は奇数, かつ, ww は bb で終わる } 3 ww ww は偶数, かつ, # aa ww は奇数, Hint: 上記の言語は全て 2 つのより簡単な言語の共通部分である

158 3. 非決定性有限オートマトン (1) 今までの fa ( 決定性有限オートマトン dfa): 現在の状態と 読む入力記号から 一意的に次の状態が定まる 非決定性有限オートマトン (nfa): 次の状態として二つ以上の可能性があってもよい 例 : ( 次の行先が無くてもよい ),1 ss 1 ss 1 ss 2 1 ss 3 ss 4 ss 5

159 3. 非決定性有限オートマトン (2) 定義 : 非決定性有限オートマトン (nfa) MM = KK, Σ, δδ, ss, FF 状態遷移関数 δδ が dfa と異なり 状態の集合への写像になる : δδ: KK Σ 2 KK 例,1 2 KK : べき集合 ( KK の全ての部分集合からなる集合 ) ss 1 ss 1 ss 2 1 ss 3 ss 4 ss 5 δδ ss, 1 = ss, ss 1, δδ ss 1, 1 =, δδ ss 2, =, など

160 3. 非決定性有限オートマトン (3) 非決定性有限オートマトン (nfa) MM = KK, Σ, δδ, ss, FF 状態遷移関数 δδ: KK Σ 2 KK に対して 写像 δδδ: KK Σ 2 KK を以下のように再帰的に定義する : ss KK, xx Σ, aa Σ に対して 1 δδ ss, εε = ss 2 δδ ss, xxxx = qq KK pp KK pp δδδ ss, xx かつ qq δδ pp, aa 例 = pp δδ ss,xx δδ pp, aa

161 3. 非決定性有限オートマトン (4) 1 δδ ss, εε = ss 2 δδ ss, xxxx = qq KK pp KK pp δδδ ss, xx かつ qq δδ pp, aa 例 δδ ss, 11 = qq KK pp KK pp δδ ss, 1 qq δδ pp, 1 } δδ ss, 1 = qq KK pp KK pp δδ ss, 1 qq δδ pp, } = qq KK pp KK pp ss, ss 1 qq δδ pp, } = δδ ss, δδ ss 1, = {ss, ss 2 } δδ ss, 11 = qq KK pp KK pp {ss, ss 2 } qq δδ pp, 1 } = δδ ss, 1 δδ ss 2, 1 = {ss, ss 1, ss 3 }

162 3. 非決定性有限オートマトン (5) δδ ss, 1 = {ss, ss 1 } を ss で 1 を読むと状態 ss と ss 1 のいずれにも行ける と解釈する δδ ss, 11 = {ss, ss 1, ss 3 } は ss で 11 を読むと状態 ss と ss 1 と ss 3 のいずれにも行ける と解釈する δδ ss 1, 1 = は ss で 1 を読むと行ける状態が存在しない と解釈する

163 3. 非決定性有限オートマトン (6) 定義 : 非決定性有限オートマトン (nfa) MM = KK, Σ, δδ, ss, FF と列 xx に対して δδ ss, xx FF のとき つまり δδ ss, xx に少なくとも一つの受理状態が含まれるときに MM は xx を受理する と呼ぶ 要するに 初期状態から列 xx を読んである受理状態に到達することができるなら 受理 である 例 : 最後が 11 で終わる列の全体を受理するオートマトン,1 ss 1 ss 1 ss 2 1 ss 3 ss 4 ss 5

164 3. 非決定性有限オートマトン (7) 例題 2.7 言語 xxxxx xx,1 を認識する nfa を与えよ 解答 :,1 1 あってもなくてもよい ss 1 1 ss 1 ss 2 1 ss 3

165 3. 非決定性有限オートマトン (8) 練習問題 : 言語 xxxxx xx,1 を認識するdfa( 決定性有限オートマトン ) を 与えよ あってもなくてもよい ヒント : 上記の言語を認識するnfa,1 1 ss 1 1 ss 1 ss 2 1 ss 3

166 3. 非決定性有限オートマトン (9) 練習問題 : 言語 xxxxx xx,1 を認識するdfa( 決定性有限オートマトン ) を 与えよ 解答 : 1 ss 1 1 ss 1 ss 2 1 ss 3

167 3. 非決定性有限オートマトン (1) 例題 : nfa が認識する言語 (11 で終わる列すべて ) を認識する dfa( 決定性有限オートマトン ) を与えよ 解答例???:,1 ss 1 ss 1 ss 2 1 ss 3 ss ,1 ss 5

168 3. 非決定性有限オートマトン (11) 例題 : nfa が認識する言語 (11 で終わる列すべて ) を認識する dfa( 決定性有限オートマトン ) を与えよ 解答例 : ss 1 ss 1 ss 2 1 ss 3 ss ,1 ss 5

169 3. 非決定性有限オートマトン (12) 例題 : 11で終わる列全てからなる言語を認識するdfaを与えよ 間違った解答例 : 例えば 言語に入っている 111 を読むと ss ss 1 ss 2 ss 3 ss 4 ss ss ss となり受理されない ss 4 ss がおかしい ss 1 は 1 を ss 2 は 1 を ss 3 は 11 を ss 4 は 11 を直前に読んだことを記憶するための状態である ss 4 で 1 を読むと 111 を読んだことになるので ss ではなく ss 3 に行かなくてはならない

170 3. 非決定性有限オートマトン (13) 例題 : 11で終わる列全てからなる言語を認識するdfaを与えよ 改良した解答例??: ss 1 ss 1 ss 2 1 ss 3 ss ,1 ss 5 まだ 三つ間違いが残っている ss 1 は 1 を ss 2 は 1 を ss 3 は 11 を ss 4 は 11 を直前に読んだことを記憶するための状態である

171 3. 非決定性有限オートマトン (15) 例題 : 11で終わる列全てからなる言語を認識するdfaを与えよ 本当に正しい解答例 1 ss 1 ss 1 ss 2 1 ss 3 ss ss 5 ss 1 は 1 を ss 2 は 1 を ss 3 は 11 を ss 4 は 11 を直前に読んだことを記憶するための状態である

172 3. 非決定性有限オートマトン (16) 今までのfaの1ステップは 以下の三つの動作からなる : 1 入力を読む 2 ヘッドを (1コマ右に) 動かす 3 状態を変える ( 状態遷移関数にしたがって ) 2 ヘッドを動かす ことをしないことを許す つまり 入力を読まずに状態を変えることができる オートマトンを考える : ε 入力付非決定性有限オートマトン (εnfa)

173 3. 非決定性有限オートマトン (17) ε 入力付非決定性有限オートマトン (εnfa) 1 ss ss 1 ss 3,1 ss 1 から入力を読まずに ( ヘッドを動かさずに ) ss 4 へ遷移することができる 1 ε ε 1 ss 2 ss 4 ε 状態が ss 1 でヘッドの下の記号が なら ss 3 に行ってヘッドを右に一つ動かす他に ヘッドを動かさずに ss 2, ss 4 に遷移することも可能

174 3. 非決定性有限オートマトン (18) 定義 ε 入力付非決定性有限オートマトン (εnfa) MM = (KK, Σ, δδ, ss, FF) nfa との違いは δδ の定義域が KK Σ εε となっていること つまり δδ: KK Σ εε 2 KK 右の例なら δδ ss 1, = ss 3, δδ ss 1, εε = {ss 2, ss 4 }, テープを読み終わったときに 受理状態に到達できれば受理される 例では 111 も ss ss 1 ss 2 ss ss 1 ss 3 とすれば受理される

175 3. 非決定性有限オートマトン (18) オートマトンの動作途中の状況を表すために xx Σ, pp KK に対して様相 (xx, pp) を定義する xx はテープのまだ読んでいない部分の列 pp はそのときの状態 読み終わった部分は将来の動作に影響しない 例 : まだよんでいないテープの部分 様相 11, ss ss 5

176 3. 非決定性有限オートマトン (19) 定義 : 以下の (i) もしくは (ii) を満たすとき 様相 cc 1 = (xx 1, pp 1 ) から様相 cc 2 = (xx 2, pp 2 ) へ 1 ステップで移れる (cc 1 cc 2 と書く ) と呼ぶ : (i) xx 1 = xx 2 かつ pp 2 δδ pp 1, εε (ii) aa Σ に対して xx 1 = aaxx 2 かつ pp 2 δδ pp 1, aa 例 : 11, ss 1 (11, ss 3 ) 11, ss 1 11, ss 4 である

177 3. 非決定性有限オートマトン (2) 定義 :cc cc 1 cc kk のとき 様相 cc から cc kk へ何ステップかで移れる (cc cc kk と書く ) と呼ぶ ステップの場合も含む ( つまり cc = cc kk のとき ) 定義 : 列 xx Σ は 初期状態 ss ある受理状態 ss FF に対し xx, ss εε, ss FF であるとき受理されると呼ぶ この定義より 最後が εε 入力でも受理される : xx, ss εε, ss εε, ss FF で ss FF でも xx は受理される

178 3. 非決定性有限オートマトン (21) 練習問題 : 左図のオートマトンで 列 11 が受理されることを示せ ヒント : 11, ss (εε, ss 3 ) の形の様相の列を作ればよい

179 3. 非決定性有限オートマトン (22) 練習問題 : 左図のオートマトンで 列 11 が受理されることを示せ ( 解答例 ) 11, ss 1, ss 1 1, ss 4 1, ss, ss 1 (εε, ss 3 )

180 4. 有限オートマトンと正規表現の等価性 (1) 定義正規表現を持つ言語を正規言語と呼ぶ この節の目的 : ( 決定性 ) 有限オートマトン (dfa) と正規表現が等価であることを示す 任意の言語 LL に対して LL が dfa で認識可能であることは LL が正規言語であることの必要十分条件 証明の方針 :dfa nfa εnfa 正規言語の集合を L dfa L nfa L εεεεfa L( 正規言語 ) と書く L dfa = L nfa = L εεεεfa = L( 正規言語 ) を証明することを目指す

181 4. 有限オートマトンと正規表現の等価性 (2) L dfa = L nfa = L εεεεfa = L( 正規言語 ) を証明することを目指す dfa は特殊な nfa nfa は特殊な εnfa なので L dfa L nfa L εεεεfa は明らか nfa が dfa で模倣できる こと (LL L nfa LL L dfa ) と ( nfa の動作を fa で 真似 して同じ言語を認識するようにできる ) εnfa が nfa で模倣できる こと (LL L εεnfa LL L nfa ) を証明した後で L εεεεfa = L( 正規表現 ) を証明すればよい

182 4. 有限オートマトンと正規表現の等価性 (3) 補題 2.1 言語 LL が nfa で認識できるならば dfa でも認識できる ( 証明の概要 ) 与えられた nfa NN に対し それが認識する言語を変えずに dfa DD に直せることを示す < アイデア : 部分集合構成 > NN にテープを途中まで読ませたときに 到達可能な状態の集合を SS 1 KK とする ここから さらに記号 aa を読んだときに到達できる状態の集合 SS 2 は以下で与えられる SS 2 = qq pp SS 1 qq δδ pp, aa SS 1 と SS 2 を単独の状態とみなす ( 群状態 ) ことで SS 1 から SS 2 へ入力記号 aa を読むことで決定的に遷移する dfa DD が得られる 初期状態は {ss } とし NN の受理状態を一つでも含む状態集合を DD の受理状態とする

183 4. 有限オートマトンと正規表現の等価性 (4),1 SS 2 = qq pp SS 1 qq δδ pp, aa ss 1 1, ss 1 ss 2 1, ss 3 1, ss 4 に対応する dfa を部分集合構成で作る : {ss } 1 1 {ss, ss 1 } {ss, ss 2 } {ss, ss 3 } {ss, ss 4 } {ss, ss 1, ss 2 } {ss, ss 1, ss 3 } {ss, ss 1, ss 4 } 途中まで ( 未完成 )

184 4. 有限オートマトンと正規表現の等価性 (6) 補題 2.2 言語 LL が εnfa で認識できるならば nfa でも認識できる ( 証明の概要 ) 与えられた εnfa EE に対し それが認識する言語を変えずに nfa NN に直せることを示す < アイデア > 状態は同じで 遷移 εε を消して 通常の遷移 aa で置き換えたい EEの状態 ssに対して ssから入力信号を読まないで ( εε で ) 遷移できる状態の集合をSS ss とする ss, SS ss をssに対応するNNの状態とする あるtt 1 SS ss に対して tt 1 からtt 2 へ記号 aa( εε) によるEEの遷移が存 在するときに限って 状態 ss, SS ss から tt 2, SS tt 2 へ記号 aaで遷移 できるとする ss, SS ss aa tt 2, SS tt 2 tt 1 SS ss tt 1 aa tt 2

185 4. 有限オートマトンと正規表現の等価性 (7) 初期状態は ss, SS ss 例 : とする ss, SS ss aa tt 2, SS tt 2 tt 1 SS ss tt 1 aa tt 2 1,1 (ss, {ss }) 1 (ss 1, {ss, ss 1, ss 2, ss 4 }) (ss 3, {ss 3 }) (ss 2, {ss 2 }) (ss 4, {ss, ss 4 })

186 4. 有限オートマトンと正規表現の等価性 (8) ここまでで LL dfa = LL nfa = LL εεεεfa が証明できたので LL 正規言語 LL εεεεfa と LL nfa LL 正規言語を示せば完成 補題 2.3 言語 LL が正規言語なら LL はある εεnfa EE によって認識される 証明 : 一般に 正規表現 RR は 別の正規表現 RR 1 と RR 2 を使って RR 1 + RR 2, RR 1 RR 2, RR 1 のどれかの形に書くことができる 例えば RR = は RR 1 = , RR 2 = に対して RR = RR 1 RR 2 と書ける

187 4. 有限オートマトンと正規表現の等価性 (9) RR = は RR 1 = , RR 2 = に対してRR = RR 1 RR 2 と書ける RR 3 = とすると RR 1 = RR 3 と書ける これを続けてどんどん RR 4, RR 5, RR 6 を作っていくと RR 5, RR 6 はどんどん簡単になる 最終的に これ以上分解できない以下の 3 通りの正規表現になる : や 1 のような 1 個の記号 空列 εε 空集合

188 4. 有限オートマトンと正規表現の等価性 (1) こうして得られた分解を元に RR に対応する εnfa を構成する 1 個の初期状態と受理状態を矢で結ぶ RR これを 正規表現の分解 RR 1 + RR 2, RR 1 RR 2, RR 1 に対応して下記で置き換えていく RR 1 RR 2 RR 1 εε RR 2

189 4. 有限オートマトンと正規表現の等価性 (11) これを 正規表現の分解 RR 1 + RR 2, RR 1 RR 2, RR 1 に対応して下記で置き換えていく RR 1 RR 2 RR 1 εε RR 2 RR 1 εε RR 1 εε RR 1 RR 1 + RR 2 εε εε RR 2 εε εε εε εε

190 4. 有限オートマトンと正規表現の等価性 (12) この置き換えを続けていくと 最終的に各矢の上について いるのは 1 個の記号 εε の何れかになる の場合のみ その矢を取り去る これで εnfa が完成する どうしてこの方法が正しいのか?

191 4. 有限オートマトンと正規表現の等価性 (13) どうしてこの方法が正しいのか? RR 最初の遷移図を LL RR に入る文字列を読むと初期状態から受理状態に遷移できると解釈する RR 1 RR 2 RR 1 εε RR 2 左は LL RR 1 RR 2 に入る文字列 xxxx を読むと遷移できる 右は xx LL(RR 1 ) を読んで ( 最初の矢 ) から yy LL(RR 2 ) を読む ( 最後の矢 ) と遷移できる

192 4. 有限オートマトンと正規表現の等価性 (14) RR 1 εε RR 1 εε 左は LL RR 1 に入る文字列を読むと遷移できる 右は LL(RR 1 ) に入る文字列を何回か ( 回でもよい ) 読むと遷移できる εε RR 1 εε RR 1 + RR 2 εε RR 2 εε εε εε 左は LL RR 1 + RR 2 = LL RR 1 LL(RR 2 ) に入る文字列を読むと遷移 右は LL(RR 1 ) に入る文字列もしくは LL(RR 2 ) に入る文字列を読むと遷移

193 4. 有限オートマトンと正規表現の等価性 (15) 結局 これらの置き換えを行っても 初期状態から受理状態へ与えられた正規表現 RR で表現される言語に属する列を読んで遷移する という事実が保存される つまり 受理される列は変わらない よって この置き換えを続けて最終的に得られた εεnfa は 言語 LL(RR) を認識する

194 4. 有限オートマトンと正規表現の等価性 (16) 例 : 正規表現 1 + が表現する言語を認識する εεnfa 1 + εε 1 + εε εε εε εε εε 1 + εε εε εε εε

195 4. 有限オートマトンと正規表現の等価性 (17) 例 : 正規表現 1 + が表現する言語を認識する εεnfa εε εε εε εε εε εε εε εε 1 εε εε εε εε εε

196 4. 有限オートマトンと正規表現の等価性 (18) 例 : 正規表現 1 + が表現する言語を認識する εεnfa εε εε εε εε εε εε εε εε εε 1 εε εε εε εε εε εε εε εε εε

197 4. 有限オートマトンと正規表現の等価性 (19) 例 : 正規表現 1 + が表現する言語を認識する εεnfa εε εε εε εε εε εε εε εε 1 εε εε εε εε εε εε εε εε εε εε

198 4. 有限オートマトンと正規表現の等価性 (19) 例 : 正規表現 1 + が表現する言語を認識するεεnfa この状態は無くて良い εε この部分は初期状態 εε εε から到達ができない εε εε εε εε εε 1 εε εε εε εε εε εε εε εε εε εε

199 4. 有限オートマトンと正規表現の等価性 (2) 例 : 正規表現 1 + が表現する言語を認識する εεnfa εε εε εε εε εε εε εε εε 1 εε εε εε

200 4. 有限オートマトンと正規表現の等価性 (21) 例 : 正規表現 1 + が表現する言語を認識するεεnfa εε εε εε εε εε εε 1 εε εε εε そもそもよく考えると LL 1 + = LL 1 が成立している

201 問題 以下の正規表現で表される言語を認識する εεnfa の状態遷移図を書け ただし アルファベットは {,1} とする Hint:

202 問題 以下の正規表現で表される言語を認識する εεnfa の状態遷移図を書け ただし アルファベットは {aa, bb} とする 1 aa aaaaaa + bb 2 aa aa + aaaa aaaa 3 aa + bb bb aa aa bb bb Hint:

203 4. 有限オートマトンと正規表現の等価性 (22) 補題 2.4 (LL nfa LL 正規言語 ) 言語 LL が nfa NN で認識されるなら LL はある正規表現 RR よって表わせる ( 証明の概要 ) 与えられた nfa NN = (KK, Σ, δδ, ss, FF) の正規表現を より矢の数が少ない nfa の正規表現に帰着させていく nfa NN に対応する正規表現を RRRRRR NN で表す まず 矢が一つもない nfa は ss FF のとき RRRRRR NN = εε そうでないとき RRRRRR NN = である

204 4. 有限オートマトンと正規表現の等価性 (23) 与えられたnfa NN = (KK, Σ, δδ, ss, FF) の矢の一つに注目する 1 ss ss 1 ss ss 2 ss 4 この矢を一つ取り除いた nfa を MM とする 1 ss ss 1 ss ss 2 ss 4

205 4. 有限オートマトンと正規表現の等価性 (24) MM の初期状態を vv に受理状態集合を VV に変更した nfa を MM(vv, VV) とする つまり MM = MM ss, FF 例えば : MM(ss, {ss 2 }) 1 ss ss 1 ss ss ss 2 4 MM(ss 4, FF) 1 ss ss 1 ss ss 2 ss 4

206 4. 有限オートマトンと正規表現の等価性 (25) NN: で認識される言語は を1 回も通らないで認識される言語にを1 回以上通って認識される言語を加えたものである

207 4. 有限オートマトンと正規表現の等価性 (26) を 1 回も通らないで認識される言語 とは NN から を除いた MM: で認識される言語である

208 4. 有限オートマトンと正規表現の等価性 (27) を 1 回以上通って認識される言語は を 1 回通って認識される言語と を 2 回通って認識される言語と を 3 回通って認識される言語と を全て合わせたものである

209 4. 有限オートマトンと正規表現の等価性 (28) を 1 回通って認識される言語は で認識される言語と で認識される言語と で認識される言語を連接したものである

210 4. 有限オートマトンと正規表現の等価性 (29) を 2 回通って認識される言語は で認識される言語と の言語と の言語と の言語と の言語を連接したもの

211 4. 有限オートマトンと正規表現の等価性 (3) を 3 回通って認識される言語は で認識される言語と 2 の言語との言語と の言語と の言語を連接したもの

212 4. 有限オートマトンと正規表現の等価性 (31) を nn 回通って認識される言語は で認識される言語と nn 1 の言語との言語と の言語と の言語を連接したもの

213 4. 有限オートマトンと正規表現の等価性 (32) を 1 回以上通って認識される言語は で認識される言語と の言語との言語と の言語と の言語を連接したもの

214 4. 有限オートマトンと正規表現の等価性 (33) 結局 で認識される言語は で認識される言語と の言語と の言語との言語と の言語と の言語の連接の足し算

215 4. 有限オートマトンと正規表現の等価性 (34) よって RRRRRR = RRRRRR +RRRRRR RRRRRR RRRRRR

216 4. 有限オートマトンと正規表現の等価性 (35) 書き直すと ( 状態の名前を変えて とする ) RRRRRR NN = RRRRRR MM ss, FF +RRRRRR MM ss, ss aa RRRRRR MM ss, ss aa ss ss aa RRRRRR MM ss, FF ここで NN は aa ss ss MM は MM の初期状態を vv に受理状態集合を VV に変更した nfa を MM(vv, VV) とする つまり MM = MM ss, FF また を aa と書いた

217 4. 有限オートマトンと正規表現の等価性 (36) 書き直すと ( 状態の名前を変えて とする ) RRRRRR NN = RRRRRR MM ss, FF +RRRRRR MM ss, ss aa RRRRRR MM ss, ss aa ss ss aa RRRRRR MM ss, FF MM は NN よりも矢の数が 1 本少ないので NN の正規表現を 矢の数が 1 つ少ない nfa の正規表現に帰着できた 実は 上記の式はどんな nfa のどんな矢に対しても成立する よって この式を何度も使うことで 最終的に矢の一つもない nfa の正規表現に帰着できる 矢が一つもない nfa は ss FF のとき RRRRRR NN = εε そうでないとき RRRRRR NN = である よって この方法で任意の nfa の正規表現が求まる

218 4. 有限オートマトンと正規表現の等価性 (37) よって LL nfa LL 正規言語が証明できた すでに LL 正規言語 LL dfa = LL nfa = LL εεεεfa は証明しておいたので 結局 LL dfa = LL nfa = LL εεεεfa = LL( 正規言語 ) が証明できた 定理 : fa と正規表現は等価である 即ち fa で認識できる言語は正規表現で生成できるし 逆もまた真である 正規言語 : 有限オートマトンで認識できる (= 正規表現を持つ ) 言語

219 5. 有限オートマトンの能力の限界 (1) 有限オートマトン 正規表現は 様々な場面 用途で使われており重要である しかし 言語表現能力は低い 例えば カッコ文 (((( )))) が左カッコ ( の数 = 右カッコ ) の数という性質を持つかどうかを確かめたいとする ( を, ) を 1 として 言語 nn 1 nn nn } は fa で認識できるか? 定理 : 言語 nn 1 nn nn } はいかなる fa によっても認識できない 証明は次のページ

220 5. 有限オートマトンの能力の限界 (2) ( 証明 ) 鳩ノ巣原理を使う 言語 mm 1 mm mm } がfa MMによって認識できたとする MMの状態数をnnとする 状態 tt ii を tt ii δδ ss, ii で定義する 状態数が nn なので tt, tt 1,, tt nn+1 の中に少なくとも 2 個の同じ状態が含まれる これらを tt ll と tt ll+kk とする (tt ll = tt ll+kk ) MM は列 ll 1 ll を受理する よって δδ(tt ll, 1 ll ) は受理状態 ll kk しかし tt ll = tt ll+kk なので δδ tt ll, 1 ll = δδ tt ll+kk, 1 ll よって ll+kk 1 ll も受理される これは矛盾 1 ll tt ll = tt kk+ll

221 5. 有限オートマトンの能力の限界 (3) 例 2.13: 言語 xxxx ( 証明 ) xx,1 } はいかなる fa によっても認識できない 同様に鳩ノ巣原理で証明できる この言語を認識できる fa MM を考える MM の状態の数を nn とする MM は 1 nn 1 nn を認識するので 状態遷移関数 δδ を用いて tt = ss, tt 1 = δδ ss, 1 tt ii = δδ ss, 1 ii 1 とする tt, tt 1,, tt nn のうち 同じ状態が少なくとも 2 個ある それを tt ll と tt ll+kk とする (kk 1 ) i) ll = のとき : δδ tt, 1 nn 1 nn = δδ(tt kk, 1 nn 1 nn ) は受理状態 これでは 1 k 1 1 nn 1 nn を受理するので矛盾 ii) ll 1のとき : δδ tt ll, nn ll+1 1 nn = δδ tt ll+kk, nn ll+1 1 nn が受理状態 この場合 1 ll+kk 1 nn ll+1 1 nn = 1 nn+kk 1 nn が受理され矛盾 よって この言語はfaでは認識できない