情報数理学

Size: px

Start display at page:

Download "情報数理学"

ゆきひらそや
4 years ago
Views:

1 2007 年度情報数理学

2 履修にあたって 2007 年度大学院奇数セメスター ( 前期 ) 開講教室 : K336 大学院棟 D46( 次回から ) 時限 : 火曜日 3 時限 (2:50-4:20) 担当草苅良至 2

3 講義予定計算機のいろいろな理論モデル言語理論計算の限界問題の難しさ現実問題と計算計算量理論アルゴリズム論 3

4 参考書 M. Sipser 著計算理論の基礎共立出版 997,ISBN: 岩間一雄オートマトン言語と計算理論コロナ社 2003 ISBN: X 岩間一雄アルゴリズム理論入門昭晃堂 200 ISBN: ホップクロフトウルマンオートマトン言語理論計算論 I,II サイエンス社 984,ISBN: , M.R. Garey and D.S.Johnson, "Computers And Intractability:A guide to the Theoryof NP-Completeness," Freeman,979,ISBN: V.V. ヴィジラーニ著浅野孝夫訳近似アルゴリズムシュプリンガーフェアラーク東京 2002 ISBN:

5 . オートマトンと正規表現 5

6 -. 有限オートマトンメモリがほとんどなくはいといいえしか答えられない計算機を考える自動機械 0 入力テープランプ 0 入力テープを一度だけ走査したあとはいならランプ点灯いいえならランプ消灯このような自動機械を ( 有限 ) オートマトンという 6

7 有限オートマトンの概略テープヘッド 0 有限制御部オートマトンを定める要素入力テープテープに書ける文字有限制御部内部状態初期状態状態変化受理かどうかの判断 7

8 有限オートマトンの数学的定義有限オートマトンはここで M = ( Q, Σ, δ, q, F) 0 の 5 項組で与えられる. Q は有限集合で状態を表す 2. Σ は有限集合で入力記号の集合を表す 3. δ は Q Σ から Q への写像 ( δ : Q Σ Q ) で状態遷移を表す δ を状態遷移関数という 4. q0 Q は初期状態を表す 5. F Q は受理状態の集合を表すとする 8

9 有限オートマトンの図式表現 ( 状態遷移図 ) 有限オートマトンは状態遷移図で表現できるオートマトン例 0 M q このオートマトンの形式的定義 ( 数学的定義 ) は M = ({ q, q },{0,}, δ, q,{ q }) 2 2 であり δ は次の状態遷移表により定義される δ 0 q q q 2 q q q q 2 9

10 練習次のオートマトンの数学的表現を与えよ M q 0 q 2 0 q 0 3 0

11 -2. 言語ここで計算機で扱える対象について再考する計算機が扱える対象は {0,} で表された数と考えがちであるしかし {0,} の並びを一種の言語とみなすこともできる以下では言語の数学的定義を与える任意の有限集合をアルファベットというアルファベットの要素を文字というアルファベットの任意の列を文字列という文字列の集合を ( アルファベット上の ) 言語という

12 言語の例アルファベット例 : Σ = {a,b,c,d,,z,( スペース ),( ピリオド )} Σ 上の文字列例 : a aa ab book Σ 上の言語例 : L = { w wは a で始まる文字列 } = {a,aa,ab,ac,ad,,a,a.,aaa, } L 2 = {this,that,is,a,pen,this is a pen.,that is a pen.} L 3 = { 全ての英単語 } { Σ } L = ( 以外の記号を無視した ) 全ての英文 4 2

13 言語の例 2 アルファベット例 : Σ 2 = {0,} Σ 上の文字列例 : Σ 上の言語例 : 2 L3 = { w wはで終わる文字列 } = {, 0,, 00, 0,0,, } L4 = { w wはが奇数個である文字列 } = {,0,0,00,00,00,, , } 3

14 言語に関する諸概念ここでは文字列に関する諸概念の定義を与える文字列の長さ : 文字列 w に含まれる文字数を文字列 w の長さといい w という記号で表す空列 : 長さが0の文字列を空列といい記号 ε で表す連結 : 文字列 xの後ろに文字列 y を繋げてえられる文字列をとの連結といい次のような記号で表す x y xy x y k x = xx x k 4

15 例 Σ 2 = {0,} 上の文字列を考える w= 0, x= 0, y = 00 とするこのとき次式が成り立つ w = 2, x = 3, y = 5 w 0 = x 0 = y 0 = ε ε = 0 y = wx y xw 文字列の連結演算は交換不可 w = 00, w =

16 言語に関する諸概念 2 ここでは言語に関する諸概念の定義を与える A と B を言語とする言語の和集合 ( 和集合演算 ): A B = { x x Aまたはx B} 言語の連結 ( 連結演算 ): A B = AB = { xy x Aかつy B} 言語の閉包 ( スター演算 ): * A = xx 2 xk k かつ xx2 xk A { 0,,, } 6

17 例 Σ 2 = {0,} L = {0,}, 上の言語を考える L 2 = {0,} このとき次式が成り立つとする L L2 = {0,, 0,} L L 2 = {00,0,} 0 L = {}, ε 2 L = L = {0,}, L = LL = {00,0,0,} * L = { ε,0,,00,0,0,,000, } 7

18 要素の無い言語と空列だけの言語要素の無い言語と空列だけの言語は異なる L = {} = φ, L = { ε} とする 2 このときである L L 2 8

19 オートマトンと言語オートマトンによって受理される入力の集合は入力記号上の言語になっている Σ オートマトン例 0 M q q 2 0 このオートマトン M で受理される言語をと書く L( M ) 例えば LM ( ) = { w wはで終わる文字列 } である 9

20 練習次の言語を受理するオートマトン M を作成せよ LM ( ) = { w wは 0で終わる文字列 } オートマトンは状態遷移図および形式的定義の両方で示す事 20

21 -3. 非決定性 ( 有限 ) オートマトンオートマトンでは入力記号にしたがって状態遷移は一意に定められていたこの制限を緩和した計算機モデルが考えられる非決定性オートマトンとは同じ入力に対して複数の遷移をゆるすオートマトンであるこれに対して同じ入力に対して一つの遷移しかおこなえないオートマトンを決定性オートマトンという 2

22 オートマトンの略記決定性オートマトンは英語では Deterministic Finite Automaton であり DFA と略記される非決定性オートマトンは英語では Non-determinisc Finite Automaton であり NFA と略記される 22

23 NFA の形式的定義非決定性有限オートマトンは N = ( Q, Σ, δ ', q0, F) で与えられるここでの 5 項組. Q は有限集合で状態を表す 2. Σ は有限集合で入力記号の集合を表す 3. δ ' は Q Σ から P ( Q) への写像 δ ': Q Σ P ( Q) で状態遷移を表す δ を状態遷移関数という 4. q0 Qは初期状態を表す 5. F Q は受理状態の集合を表すとする 23

24 NFA の状態遷移図 N q 0, 0, 0, q 2 q3 q4 このオートマトンの形式的定義 ( 数学的定義 ) は N = ({ q, q, q, q },{0,}, δ, q,{ q }) であり δ は次の状態遷移表により定義される δ 0 q q q, q q2 q3 q3 q3 q4 q4 q φ φ { } { } 2 4 { } { } { } { } 24

25 N L N ( ) このオートマトンで受理される言語は LN ( ) である wは最後から3 文字目が, w = である文字列実は非決定性オートマトンが受理する言語と同じ言語を受理する決定性オートマトンが常に存在するモデル自体の能力に差がないあとで証明する 25

26 言語 wは最後から3 文字目が, w である文字列 M 2 DFA を示す M 2 q q 00 q 00 q 0 を受理する q 00 q 0 q 0 q 26

27 練習 Σ= {0,} 上の言語 wは最後から2 文字目が, w である文字列を受理する非決定性オートマトンと決定性オートマトンを示せ 27

28 DFA と NFA の状態遷移 M N 2 と調べる入力 : 00 入力を例にして DFA と NFA の状態遷移をとする M N 2 q 000 q q 00 q q q 0 q 0 q 00 q q q 2 q q 4 q 3 q q4 3 28

29 NFA の受理 NFA の受理とは入力系列を受理する遷移の系列が存在することである q 受理系列 qqqqq q q 2 N q q 2 q 3 q q q4 3 q q 4 29

30 練習 M N 2 とに対して入力 0の状態遷移を木によって示し受理か不受理かを確認せよ 30

31 -4. 正規表現 ( 正則表現 ) DFA で受理できる言語に対して正規表現と呼ばれる別の表現法が知られている正規表現の形式的定義 Σ をアルファベットとする Σ 上の正規表現とは下記の4つにより帰納的に定義される φ. でその表す集合は空集合である ε {} ε Σ a {} a 2. でその表す集合はである 3. の各元に対しては正規表現でその表す集合はである r s R S 4. とがそれぞれ言語と言語を表す正規表現のとき ( r+ s),( rs),( r*) は正規表現でそれぞれ * を表す R SRSR,, a 3

32 正規演算の優先順位正規表現の演算記号に優先順位をつけることによって括弧を省略できる * +< < <() 通常は上のように優先順位があると考えて不必要な括弧は省略する 32

33 例アルファベット Σ = {0,} 上の正規表現を考える ε = {}, ε 0 = {0}, = {}, 0 = {0}, 0 = {0} ε = {}, 0+ = {0,}, 0+ 0 = {0,0}, ( + 0)(0+ 0) = {0,0,00,00} * = { ε,,,,,, } * 0 = {0, 0, 0, 0, 0, 0, } Σ = (0 + ) * * = {0,} * = { ε,0,,00,0,0,,000,00, } = { 全ての2 進数 } 33

34 練習アルファベットを Σ = {a,b,c,d,,z} とするこのとき次の正規表現で表される言語に含まれる文字列をいくつか示しその直感的な意味を述べよ () m(a+e)n (2) (3) (4) (5) * bo * aσ Σ bσ * * ( a+ b+ c) * 34

35 正規表現の応用 UNIX シェルでは正規表現で引数を指定できるただし UNIX の正規表現は UNIX 独特のものなので注意する *: 任意の文字列を表す Σ * +: 一文字以上の文字列 [ cc c ] 2 n [ c c ] n * Σ c c n c+ c2 + + c n {} ε : からまでのいずれかの文字 ( ) : c から c n までのいずれかの文字 ( c+ c2 + + c n ) 35

36 例 ~$ls *.c average.c hello.c sort.c sum.c ~$ls [ab]* average average.c ~$ls [h-s]*.c hello.c sort.c sum.c ~$ *.c は.c で終わる文字列 ( 拡張子で区別すると特定種類のファイルだけを指定できる ) [ab]* はaかbで始まる文字列 ( 長いファイル名を一括して扱える ) [h-s]*.cはhからsのどれかの文字で始まり.cで終わる文字列 ( 組み合わせてファイルを絞り込める ) 36

37 -5. 拡張 NFA DFA NFA 共に入力記号文字に対してつの遷移を行っていたこの制限を緩和した計算機モデルが考えられる拡張 NFA とは遷移のラベルとして正規表現を許す NFA である拡張 NFA:Generalized Non-deterministic finite Automaton なので GNFA と略する 37

38 GNFA の形式的定義 GNFAは G = ( Q, Σ, δ, qs, qa ) で与えられるここでの 5 項組. Q は有限集合で状態を表す 2. Σ は有限集合で入力記号の集合を表す 3. は Q { q } Q { q } から R への写像 δ ( a ) ( s ) :( Q { q }) ( Q { q }) δ R a s で状態遷移を表す δ を状態遷移関数というただし R は Σ 上の正規表現すべてからなる集合 ( Σ 上の正規言語 ) を表す 4. qs Qは初期状態を表す 5. qa Q は受理状態を表すとする 38

39 GNFA の状態遷移図 G q s * (+ 0) ( + 0)( + 0) q q 2 q a このオートマトンの形式的定義 ( 数学的定義 ) はであり G = ({ q, q, q, q },{0,}, δ, q, q ) δ 2 s a s a は次の状態遷移表により定義される δ q q q s 2 q q q ( + 0) 2 * φ φ φ φ φ ( + 0)( + 0) a φ 39

40 GNFA に関する注意初期状態受理状態 q s q a には他の状態からの遷移がないからは他の状態への遷移がない初期状態と受理状態はそれぞれつづつしかない特に受理状態がつであることに注意する G q s * (+ 0) ( + 0)( + 0) q q 2 q a 入ってくる矢印 ( アーク ) が無い出て行く ( アーク ) が無い 40

41 練習 Σ= {0,} 上の言語 w wは最後から4 文字目が, 0である文字列を受理する 4 状態の拡張 NFA を状態遷移図と形式的定義の両方で示せ 4

Microsoft PowerPoint - 1.ppt [互換モード]

Microsoft PowerPoint - 1.ppt [互換モード] 第回オートマトンと正規表現 8//5( 火 ) 履修にあたって 8 年度情報数理学 8 年度大学院奇数セメスター ( 前期 ) 開講教室 : K6 大学院棟 D6( 次回から ) 担当時限 : 火曜日時限 (:5-:) 草苅良至講義予定計算機のいろいろな理論モデル言語理論計算の限界計算量理論問題の難しさ現実問題と計算アルゴリズム論参考書. Sipser 著計算理論の基礎共立出版