...

オートマトンと計算理論 第1回 (10/4)

by user

on
Category: Documents
0

views

Report

Comments

Transcript

オートマトンと計算理論 第1回 (10/4)
オートマトンと計算理論
第1回 (10/4)
火曜1・2限目
尾張 正樹
居室:J2415 (情報2号館4階)
[email protected]
講義資料: ¥¥fs.inf.in.shizuoka.ac.jp¥share¥class¥2016オートマトン
講義の基本情報
• オートマトンと計算理論について学ぶ。
• 必修科目
• メイン参考書:『オートマトン・言語と計算理論』小
岩間一雄 (コロナ社)
• サブ参考書:『アルゴリズムと計算量』
谷聖一 (サイエンス社・SGCライブラリ43)
• 基本的にメイン参考書に準じて講義を行う
• 授業の後半で、足りない部分をサブ参考書から少し補
う
評価について
期末試験のみで評価を決める。
• 試験問題の候補:N問(たぶん6≦N ≦12) を2
回に分けて事前に教える。
前半:オートマトン、後半:計算理論
• N問の中のN/3-N/2問くらいが実際に出題され
る。
• 参考書1の範囲以外からは出題しない。
• 講義に出席しなくても、参考書や授業のスライ
ドで勉強をしていれば問題は解けます。
• 再試験はやりません。(勉強無し=単位無し)
• 『原則的には』、授業中に加点減点はしない。
講義予定
1章. 形式言語の導入 (1回)
2章. 正規表現と有限オートマトン (2-3回)
3章. 文脈自由文法 (4-5回)
4章. プッシュダウンオートマトン (6-7回)
5章. チューリング機械と0型文法 (8-9回)
6章. チューリング機械の停止性と決定問題 (10-11
回)
7章. NP完全問題 (12-13回)
8章. 発展的話題 (14-15回)
講義予定
オートマトンと言語理論
1章. 形式言語の導入 (1回)
2章. 正規表現と有限オートマトン (2-3回)
3章. 文脈自由文法 (4-5回)
4章. プッシュダウンオートマトン (6-7回)
5章. チューリング機械と0型文法 (8-9回)
6章. チューリング機械の停止性と決定問題 (10-11
回)
7章. NP完全問題 (12-13回)
8章. 発展的話題 (14-15回)
計算理論
講義全体の前3分の2
=オートマトンと言語理論
主題は2つ
オートマトン:計算機のモデル(抽象機械)
• 有限オートマトン
• プッシュダウンオートマトン
• チューリング機械
形式言語: (プログラミング)言語のモデル
• 正規表現 ⇔正規言語⇔正規文法
• 文脈自由文法⇔文脈自由言語
• 0型文法⇔0型言語
言語のモデルと計算機のモデルの対応を理解する。
講義全体の後ろ3分の1
=計算理論
計算模型やアルゴリズムを理論的に扱う分野
計算可能性理論
与えられた問題がコンピュータで解けるか?
⇒チューリング機械の停止性問題
計算複雑性理論
時間計算量:計算にかかるステップ数
空間計算量:計算に必要なメモリ量
特に計算量クラスNPについて詳しく抗議する。
この講義が何の役に立つの?
計算機の原理を理解することで、
『計算機に負けない体を作る』
オートマトン⇒半導体設計の自動化、言語処理
通信プロトコル設計、構文解析
言語理論⇒プログラミング言語、
コンパイラ ≃ 言語処理、
自然言語処理
計算理論⇒アルゴリズム設計の指針、など
第一章:形式言語の導入
1. 文章の意味を理解する
2. 文章の正しさを理解する
3. 形式言語を導入する
1.文章の意味を理解する (1)
計算機に文章の意味を理解させるにはどうし
たらよいか?
数式を文章の例にとって考える:
15 + 30
23 +
× (8 + 13)
7+2⋅4
二つの数の加減乗除しか知らない小学生に
この計算の仕方を教えよう!
1.文章の意味を理解する (2)
木をつかって数式(文章)を記述する
木=連結で、閉路のない、無向グラフ
根
(親)
頂点
枝
(子)
葉
葉
葉
葉
1.文章の意味を理解する (3)
15+30
7+2⋅4
15
木をつかって23 +
+ 51 × (8 + 13)を記述
する
+ 根
頂点
23
⋅
葉
+ 枝
+
/
13
8
51
+
+
30
7
2
⋅
頂点に演算子を置く
4 葉に数字を置く
1.文章の意味を理解する (3)
葉から初めて、子から親へ計算をしていく
45
=3
15
15+30=45
15
+
30
+ 根
23
/
葉
7
+
+
⋅
枝
7 + 8 = 15
2
⋅
8 + 13 = 21
頂点
4
51
2⋅4=8
8
+
13
1.文章の意味を理解する (4)
文章: 23 +
15+30
7+2⋅4
× (8 + 13)
対応する意味:木
木があれば、式の値を
簡単に計算できる
⇔導出木と呼ぶ
文章から木を導くルールを文法と呼ぶ
2.文章の正しさを解析する(1)
文章の意味が定まるためには、文章が『正しい』必
要がある。
⇒正しい文章ってなに?
例:カッコ文
数式から数値や演算子を消しカッコだけ残した。
(()(())(())
この文章は正しいだろうか?
2.文章の正しさを解析する(2)
例:カッコ文
数式から数値や演算子を消しカッコだけ残した。
(()(())(())
この文章は正しいだろうか?
答え:正しくない
理由:左カッコ”(“が右カッコ”)”よりも多いから。
左カッコの数=右カッコの数 が必要
2.文章の正しさを解析する(3)
カッコ文の二つ目の例:
(()((()))))(()(())
この文章は正しいだろうか?
答え:正しくない
(()((()))))(()(())
赤いところだけをみると、右カッコ”)”が左カッコ”(”よ
りも多い。
既出のカッコが全て閉じられているのに、次に右カッ
コ”)”が来ている
2.文章の正しさを解析する(4)
結局:カッコ文は次の条件を満たすときに「正しい」
・文全体に対して:
左カッコ”(”の数 = 右カッコ”)”の数
・任意のnに対して、最初からn文字目までで、
左カッコ”(”の数 ≥ 右カッコ”)”の数
練習:カッコ文の正しさを検証するにはどうしたら良
いか考えよ。
ヒント:スタックを使うと簡単
2.文章の正しさを解析する(5)
練習:カッコ文の正しさを検証するにはどうしたら良いか考え
よ。
解答例:
カッコ文を左から読んでいく。
左カッコを読む ⇒ スタックを一つ積む
右カッコを読む ⇒ スタックを一つ取り出す
スタックが空のとき、右カッコを読むと、
『正しくない』と判断
最後まで文を読んだとき、スタックが空なら正しいと判断
(プッシュダウンオートマトンの簡単な例になっている)
3.形式言語の導入(1)
形式言語: (プログラミング or 人工)言語の(数学的)モデル
文字 (もしくは記号)
日本語:ひらがな、カタカタ、漢字
形式言語:0,1,a,b,c,… などの数字やローマ字
アルファベット
⇔記号の有限集合
例: 0,1 , {, , } など
この授業では、アルファベットをΣ (シグマ)で通常表す。
3.形式言語の導入(2)
アルファベット Σ 上の列(もしくは文章もしくは記号列)
:= Σ上の記号を重複を許して一列に並べたもの
例:
Σ = 0,1 のとき、0, 1, 01, 10, 1011, 10010011, …などが列
列の長さ  := 列に含まれる記号の個数
例: = 01101の長さは、  = 5
空列 := 長さが0の列
よって  = 0
3.形式言語の導入(3)
列の逆  ≔ を後ろから順に読んだ列
 = 1 2 ⋯ −1  ( ∈ Σ)のとき
  =  −1 ⋯ 2 1
 =  ( ∈ Σ)のとき =   、  ≔ 
列と列の連接 := 列 の後に列をつけた列
例: = 1101,  = 000なら = 1101000
同じ列の連接:  2 : = 
空列と任意の列に対して、 =  = 
3.形式言語の導入(4)
例の続き:
3つ以上の列の連接
列, , に対して、 ≔   =  
 3 ≔ 
☆連接は結合則を満たす。
列の部分列:列の一部分の列のこと
列は列の部分列 ⇔ ある列, が存在して = 
3.形式言語の導入(5)
アルファベットΣ上の言語 := Σ上の列の集合
言語の例:
有限集合: 0,01,000,10101
無限集合: 0 1  ≥ 0} 10, 1100, 111000,….という集合
『無限集合をいかにして書き表すか』が前半の主題
言語の特別な例:
全ての列の集合:Σ ∗ 、 例えば 0,1 ∗ ≔ , 0,1,00,01,10, … ,
空集合∅ : どのような列も含まない言語
空列集合  : 空列のみからなる言語
3.形式言語の導入(6)
練習問題
以下はどのような言語であるか推測しなさい。
1 = 1, 010, 00100, 0001000, 000010000, ⋯
2 = {, 00, 11, 0000, 0101, 1010, 1111, 000000,
001001, 010010, 011011, ⋯ }
3 = {1, 010, 011, 110, 111, 00100, 00101, 00110, 00111,
01100, 01101, 01110, 01111, 10100, 10101, 10110,
10111, 11100, 11101, 11110, 11111, 0001000, 0001001, ⋯ }
3.形式言語の導入(6)
解答例
1 = 1, 010, 00100, 0001000, 000010000, ⋯
= 0 10  ≥ 0}
☆この授業ではは整数にしか用いないとする。
2 = {, 00, 11, 0000, 0101, 1010, 1111, 000000,
001001, 010010, 011011, ⋯ }
=   ∈ Σ ∗ }
3 = {1 010, 011, 110, 111, 00100, 00101, 00110, 00111,
01100, 01101, 01110, 01111, 10100, 10101, 10110,
10111, 11100, 11101, 11110, 11111, 0001000, 0001001, ⋯ }
=  ,  ∈ Σ ∗ ,  = ||}
3.形式言語の導入(7)
例題1.2 列 ∈ Σ ∗ の逆をより形式的に定義せよ。
解答
再帰的定義を用いる。
逆  は、以下の(i)と(ii)により再帰的に定義される:
(i)   = 
(ii) 列 ∈ Σ ∗ と記号(長さ1の列) ∈ Σに対して、 
例:   に上記の定義を適応する


 =  
=    =  

=    =    =  = 


=   
 =   
3.形式言語の導入(8)
練習問題
列で =   を満たすものを回文と呼ぶ。
回文の再帰的定義を与えよ。
ヒント:回文を再帰的に作成するルールを考える
3.形式言語の導入(9)
練習問題
列で =   を満たすものを回文と呼ぶ。
回文の再帰的定義を与えよ。
解答
(i) 空列と長さ1の列(記号)は回文である。
(ii) 回文と記号 ∈ Σに対して、列は回文である。
(i)と(ii)を用いて生成できるものだけが回文である。
3.形式言語の導入(10)
例題1.3 とを列としたとき、   =     を証明せよ。
解答
列の長さに関する数学的帰納法で証明する。
(i)  = 0のとき、 =  = なので、
  =   =  =  =     で正しい。
(ii)  = のとき命題が正しいと仮定する。
 = のとき、   =   =    =     でOK
 ≠ のとき、ある ∈ Σが存在して、 = と書ける。
 ′ は長さなので、帰納法の仮定より  ′   =    ′


′

′
よって  =   =   
=  ′    =    ′ 
一方、    =    ′  =    ′  なのでOK
(i) (ii)よりすべてのに対して命題は証明された。
3.形式言語の導入(11)
言語1 と2 の連接1 2
1 2 ≔ 1 2 1 ∈ 1 , 2 ∈ 2 }
例:
1 = 00,100 , 2 = {1111,001}のとき、
1 2 = 001111, 00001, 1001111, 100001
空列のみの言語{}:
任意の言語に対して、   =   = 
3.形式言語の導入(12)
例題1.4 任意の言語に対して、 = ∅を示せ。
解答:
任意の列に対して、
 ∈ 1 2 ⇔ ∃1 ∃2 ( = 1 2 and 1 ∈ 1 and 2 ∈ 2 )
である。
今、2 = ∅なので2 ∈ 2 となる2 は存在しない。
したがって、” = 1 2 and 1 ∈ 1 and 2 ∈ 2 ”を満たす1 と2
の組は存在しない。1 2 = に入るは存在しない。
よって、 は空集合である。
3.形式言語の導入(13)
2 = , 3 = , と定義する。一般に = −1
特別な場合として、1 = , 0 = {}と定義する。
言語のクリーネ閉包∗ :
∗ = �  = 0 ∪ 1 ∪ 2 ⋯
≥0
“∗”のことをスター演算と呼ぶ。
Σ上の全ての列の集合Σ ∗ は、Σを長さ1の列すべてからなる言語と
考えると、言語Σのクリーネ閉包になっている。
3.形式言語の導入(14)
クリーネ閉包∗ のみで、無限言語を記述することができる:
例題1.5  = , , ,  ∗ はどんな言語か説明せよ。
解答:
 ∈ である必要十分条件は以下の4条件を満たすことである。
(i) の最初の記号はまたは (つまりではない)
(ii) にが現れたら次の記号は(もしあれば)または
(iii) にが現れたら次の記号は
(iv) は4個以上続かない (  で ≥ 4はの部分列でない)
このことを証明する。
3.形式言語の導入(15)
解答の続き1
 ∈ である必要十分条件は以下の4条件を満たすことの証明
(i) の最初の記号はまたは (つまりではない)
(ii) にが現れたら次の記号は(もしあれば)または
(iii) にが現れたら次の記号は
(iv) は4個以上続かない
 ∈  ⇒(i)-(iv) の証明:  ∈  ⇒ ∃ ≥ 0,  ∈ , , ,  
⇒  = 1 2 ⋯  で任意の ≤ に対して ∈ {, , , }
(i)は1 = {, , , }より、(ii)は ∈  なら次の記号は+1
の先頭の記号であることより、(iii)は  ∈  なら次の記号も に入
ることより、(iv)は  でが3個までしか続かなく、+1 の先頭の記
号はではないことから示せる。
3.形式言語の導入(16)
解答の続き2
(i) の最初の記号はまたは (つまりではない)
(ii) にが現れたら次の記号は(もしあれば)または
(iii) にが現れたら次の記号は
(iv) は4個以上続かない
が(i)-(iv)を満たす ⇒  ∈ の証明:
列の以下の①~⑤場所に区切りを入れる
①との間 ②との間 ③との間 ④との間
⑤列の最初と最後
(例えば、 = は    |となる。)
(i)-(iv)を満たすに対して、2個の区切りの間の部分列が、全て
, , , のいずれかに入っていることを示せれば、  ∈ を
証明できる。
3.形式言語の導入(17)
練習問題
列の以下の①~⑤場所に区切りを入れる
①との間 ②との間 ③との間 ④との間
⑤列の最初と最後
(i)-(iv)を満たす列に対して、2個の区切りの間の部分列が、全て
, , , のいずれかに入っていることを示せ。
(i) の最初の記号はまたは (つまりではない)
(ii) にが現れたら次の記号は(もしあれば)または
(iii) にが現れたら次の記号は
(iv) は4個以上続かない
3.形式言語の導入(17)
練習問題
区切り: ①との間 ②との間 ③との間 ④との間
⑤列の最初と最後
(i) 最初の記号はまたは (ii) が現れたら次の記号はまたは
 (iii) が現れたら次の記号は (iv) は4個以上続かない
解答例:区切りの間の部分列を①④、⑤③などと書くとする。
⑤①タイプの部分列: 条件(i)より
②①タイプの部分列: 条件(iii)より部分列は … と書ける。
の後ろに来て区切りがないのはのみなので、(iV)も
考慮に入れると, , しかないが、どれも最後が出ない
ので、結局このタイプの部分列は存在しない。
③②のタイプ、条件(ii)よりの後には必ず区切りがあるので
3.形式言語の導入(18)
練習問題
区切り: ①との間 ②との間 ③との間 ④との間
⑤列の最初と最後
(i) 最初の記号はまたは (ii) が現れたら次の記号はまたは
 (iii) が現れたら次の記号は (iv) は4個以上続かない
解答例の続き: 結局、全パターンを調べると以下のようになる。
部分列
部分列のタイプ

 or  or 
   or  or 
部分列が存在しない
①①,①②,①⑤,③①,③②,③⑤, ⑤①,⑤②
②③,②④,②⑤,④③,④④,④⑤,⑤③,⑤④
⑤⑤
①③,①④,②①,②②,③③,③④,④①,④②,
表より、区切りの間の部分列は全て, , , のどれか。
3.形式言語の導入(19)
例題 1.6
長さが奇数の{0,1}上の列全体からなる言語を表現せよ
解答例1:
長さが偶数の列全体は 00,01,10,11 ∗ である。これに0か1を一つ
加えて:
00,01,10,11 ∗ {0,1}
解答例2:全ての列の集合から長さが偶数の列の集合を引いて:
0,1 ∗ − 00,01,10,11 ∗
3.形式言語の導入(20)
鳩ノ巣原理:鳩が + 1羽いて巣箱が個しかないなら、必ず一つの巣
箱には2羽以上入らなければならない。
例題 1.7 を1以上の整数とし、集合はその大きさが + 1で、 ⊆
{1,2, ⋯ , 2}を満たすとする。このとき、  の元1 , 2 で、1 が2 を割り
切るものが存在することを示せ。
解答: = {1 , 2 , ⋯ , +1 }とする。各 を2で割れるだけ割って、 =
2 ⋅ と書く。ここでは奇数。よって、 ∈ 1,3, ⋯ , 2 − 1
集合 1,3, ⋯ , 2 − 1 の大きさはなのに、の大きさは + 1なので、あ
る と ( ≠ ) は、 =  を満たす。
よって、 = 2 ⋅  と = 2 ⋅  と書ける。
よって、 ≥  なら が で、 >  なら が で割り切れる。
Fly UP