理學(xué)類(lèi)情報(bào)數(shù)理學(xué)第1頁(yè)，共42頁(yè)，2023年，2月20日，星期一2履修にあたって2007年度大學(xué)院奇數(shù)セメスター（前期）開(kāi)講K336→大學(xué)院棟D４１６（次回から）教室：時(shí)限：火曜日３時(shí)限（12:50－14:20）擔(dān)當(dāng) 草苅良至第2頁(yè)，共42頁(yè)，2023年，2月20日，星期一3講義予定○計(jì)算機(jī)のいろいろな理論モデル○計(jì)算の限界○問(wèn)題の難しさ○現(xiàn)実問(wèn)題と計(jì)算言語(yǔ)理論計(jì)算量理論アルゴリズム論第3頁(yè)，共42頁(yè)，2023年，2月20日，星期一4參考書(shū)M.R.GareyandD.S.Johnson,"ComputersAndIntractability:AguidetotheTheoryofNP-Completeness,"Freeman,1979,ISBN:0-7167-1045-5巖間一雄、「アルゴリズム理論入門(mén)」昭晃堂、2001、ISBN：4-7856-3125-2ホップクロフト、ウルマン、「オートマトン?言語(yǔ)理論?計(jì)算論I,II」サイエンス社、1984,ISBN:4-7819-0374-6,4-7819-0432-7M.Sipser著、「計(jì)算理論の基礎(chǔ)」、共立出版、1997,ISBN:4-320-02948-8巖間一雄、「オートマトン?言語(yǔ)と計(jì)算理論」コロナ社、2003、ISBN：4-339-01821-XV.V.ヴィジラーニ著、淺野孝夫訳、「近似アルゴリズム」、シュプリンガー?フェアラーク東京、２００２、ISBN:4-431-70991-6第4頁(yè)，共42頁(yè)，2023年，2月20日，星期一5１．オートマトンと正規(guī)表現(xiàn)第5頁(yè)，共42頁(yè)，2023年，2月20日，星期一61－1．有限オートマトンメモリがほとんどなく、「はい」と「いいえ」しか答えられない計(jì)算機(jī)を考える。101110入力テープ自動(dòng)機(jī)械ランプ入力テープを”一度だけ“走査したあと、「はい」ならランプ點(diǎn)燈「いいえ」ならランプ消燈。このような自動(dòng)機(jī)械を(有限）オートマトンという。第6頁(yè)，共42頁(yè)，2023年，2月20日，星期一7テープ有限制御部ヘッド01有限オートマトンの概略入力テープ テープに書(shū)ける文字オートマトンを定める要素有限制御部 內(nèi)部狀態(tài) 初期狀態(tài) 狀態(tài)変化 受理かどうかの判斷第7頁(yè)，共42頁(yè)，2023年，2月20日，星期一8有限オートマトンの數(shù)學(xué)的定義有限オートマトンは、の５項(xiàng)組で與えられる。ここで、１．は有限集合で、狀態(tài)を表す。２．は有限集合で、入力記號(hào)の集合を表す。３．はからへの寫(xiě)像（）で、

狀態(tài)遷移を表す。を狀態(tài)遷移関數(shù)という。４．は、初期狀態(tài)を表す。５．は受理狀態(tài)の集合を表す。とする。第8頁(yè)，共42頁(yè)，2023年，2月20日，星期一9有限オートマトンの図式表現(xiàn)（狀態(tài)遷移図）有限オートマトンは、狀態(tài)遷移図で表現(xiàn)できる。オートマトン例0011このオートマトンの形式的定義（數(shù)學(xué)的定義）は、であり、は次の狀態(tài)遷移表により定義される。第9頁(yè)，共42頁(yè)，2023年，2月20日，星期一10練習(xí)次のオートマトンの數(shù)學(xué)的表現(xiàn)を與えよ。011001第10頁(yè)，共42頁(yè)，2023年，2月20日，星期一111－2．言語(yǔ)計(jì)算機(jī)が扱える対象は、{0,1}で表された數(shù)と考えがちである。しかし、{0,1}の並びを一種の言語(yǔ)とみなすこともできる。任意の有限集合をアルファベットという。アルファベットの要素を文字という。アルファベットの任意の列を文字列という。文字列の集合を、（アルファベット上の）言語(yǔ)という。ここで、計(jì)算機(jī)で扱える対象について再考する。以下では、言語(yǔ)の數(shù)學(xué)的定義を與える。第11頁(yè)，共42頁(yè)，2023年，2月20日，星期一12言語(yǔ)の例1アルファベット例：上の文字列例：bookaaaab上の言語(yǔ)例：第12頁(yè)，共42頁(yè)，2023年，2月20日，星期一13言語(yǔ)の例2アルファベット例：上の文字列例：000001100010001111110111上の言語(yǔ)例：第13頁(yè)，共42頁(yè)，2023年，2月20日，星期一14言語(yǔ)に関する諸概念１ここでは、文字列に関する諸概念の定義を與える。

文字列wに含まれる文字?jǐn)?shù)を、文字列wの長(zhǎng)さといい、文字列の長(zhǎng)さ：という記號(hào)で表す?？樟校洪L(zhǎng)さが0の文字列を空列といい、記號(hào)で表す。連結(jié)：

文字列

の後ろに文字列を繋げてえられる文字列をとの連結(jié)といい次のような記號(hào)で表す。第14頁(yè)，共42頁(yè)，2023年，2月20日，星期一15例上の文字列を考える。とする。このとき、次式が成り立つ。文字列の連結(jié)演算は、交換不可第15頁(yè)，共42頁(yè)，2023年，2月20日，星期一16言語(yǔ)に関する諸概念２ここでは、言語(yǔ)に関する諸概念の定義を與える。言語(yǔ)の連結(jié)（連結(jié)演算）：言語(yǔ)の閉包(スター演算）：言語(yǔ)の和集合(和集合演算）：

とを言語(yǔ)とする。第16頁(yè)，共42頁(yè)，2023年，2月20日，星期一17例上の言語(yǔ)を考える。とする。このとき、次式が成り立つ。第17頁(yè)，共42頁(yè)，2023年，2月20日，星期一18要素の無(wú)い言語(yǔ)と空列だけの言語(yǔ)要素の無(wú)い言語(yǔ)と空列だけの言語(yǔ)は異なる。とする。このとき、である。第18頁(yè)，共42頁(yè)，2023年，2月20日，星期一19オートマトンと言語(yǔ)オートマトンによって受理される入力の集合は、入力記號(hào)上の言語(yǔ)になっている。オートマトン例0011このオートマトンで受理される言語(yǔ)をと書(shū)く。例えば、である。第19頁(yè)，共42頁(yè)，2023年，2月20日，星期一20練習(xí)次の言語(yǔ)を受理するオートマトンを作成せよ。オートマトンは、狀態(tài)遷移図および、形式的定義の両方で示す事。第20頁(yè)，共42頁(yè)，2023年，2月20日，星期一211－3．非決定性(有限）オートマトンオートマトンでは、入力記號(hào)にしたがって、狀態(tài)遷移は一意に定められていた。この制限を緩和した計(jì)算機(jī)モデルが考えられる。非決定性オートマトンとは、同じ入力に対して複數(shù)の遷移をゆるす”オートマトン”である。これに対して、同じ入力に対して、一つの遷移しかおこなえない”オートマトン”を決定性オートマトンという。第21頁(yè)，共42頁(yè)，2023年，2月20日，星期一22オートマトンの略記決定性オートマトンは、英語(yǔ)では、DeterministicFiniteAutomatonであり、DFAと略記される。非決定性オートマトンは、英語(yǔ)では、Non-determiniscFiniteAutomatonであり、NFAと略記される。第22頁(yè)，共42頁(yè)，2023年，2月20日，星期一23NFAの形式的定義非決定性有限オートマトンは、の５項(xiàng)組で與えられる。ここで、１．は有限集合で、狀態(tài)を表す。２．は有限集合で、入力記號(hào)の集合を表す。３．はからへの寫(xiě)像で、狀態(tài)遷移を表す。を狀態(tài)遷移関數(shù)という。４．は、初期狀態(tài)を表す。５．は受理狀態(tài)の集合を表す。とする。第23頁(yè)，共42頁(yè)，2023年，2月20日，星期一24NFAの狀態(tài)遷移図0,110,10,1このオートマトンの形式的定義（數(shù)學(xué)的定義）は、であり、は次の狀態(tài)遷移表により定義される。第24頁(yè)，共42頁(yè)，2023年，2月20日，星期一25このオートマトンで受理される言語(yǔ)は、である。実は、非決定性オートマトンが受理する言語(yǔ)と同じ言語(yǔ)を受理する決定性オートマトンが常に存在する。モデル自體の能力に差がない。あとで、証明する。第25頁(yè)，共42頁(yè)，2023年，2月20日，星期一26言語(yǔ)を受理するDFAを示す。0110001111111000第26頁(yè)，共42頁(yè)，2023年，2月20日，星期一27練習(xí)言語(yǔ)を受理する非決定性オートマトンと決定性オートマトンを示せ。上の第27頁(yè)，共42頁(yè)，2023年，2月20日，星期一28

とを例にして、DFAとNFAの狀態(tài)遷移を調(diào)べる。DFAとNFAの狀態(tài)遷移入力：とする。入力第28頁(yè)，共42頁(yè)，2023年，2月20日，星期一29ＮＦＡの受理NFAの受理とは、入力系列を受理する遷移の系列が存在することである。受理系列第29頁(yè)，共42頁(yè)，2023年，2月20日，星期一30

とに対して、入力1011の狀態(tài)遷移を木によって示し、受理か不受理かを確認(rèn)せよ。練習(xí)第30頁(yè)，共42頁(yè)，2023年，2月20日，星期一311－４．正規(guī)表現(xiàn)(正則表現(xiàn)）DFAで受理できる言語(yǔ)に対して、正規(guī)表現(xiàn)と呼ばれる別の表現(xiàn)法が知られている。をアルファベットとする。

上の正規(guī)表現(xiàn)とは、下記の４つにより帰納的に定義される。１．で、その表す集合は、空集合である。２．で、その表す集合は、である。３．の各元に対して、は正規(guī)表現(xiàn)で、その表す集合は、である。４．とがそれぞれ言語(yǔ)と言語(yǔ)を表す正規(guī)表現(xiàn)のとき、は正規(guī)表現(xiàn)で、それぞれを表す。正規(guī)表現(xiàn)の形式的定義第31頁(yè)，共42頁(yè)，2023年，2月20日，星期一32正規(guī)演算の優(yōu)先順位正規(guī)表現(xiàn)の演算記號(hào)に優(yōu)先順位をつけることによって、括弧を省略できる。通常は、上のように優(yōu)先順位があると考えて、不必要な括弧は省略する。第32頁(yè)，共42頁(yè)，2023年，2月20日，星期一33例アルファベット上の正規(guī)表現(xiàn)を考える。第33頁(yè)，共42頁(yè)，2023年，2月20日，星期一34練習(xí)このとき、次の正規(guī)表現(xiàn)で表される言語(yǔ)に含まれる文字列をいくつか示し、その直感的な意味を述べよ。アルファベットをとする。（１）（２）（３）（４）（５）第34頁(yè)，共42頁(yè)，2023年，2月20日，星期一35正規(guī)表現(xiàn)の応用UNIXシェルでは、正規(guī)表現(xiàn)で引數(shù)を指定できる。ただし、UNIXの正規(guī)表現(xiàn)は、UNIX獨(dú)特のものなので注意する。＊：任意の文字列を表す。＋：一文字以上の文字列。：からまでのいずれかの１文字：からまでのいずれかの１文字第35頁(yè)，共42頁(yè)，2023年，2月20日，星期一36例~$ls*.caverage.c hello.c sort.c sum.c~$ls[ab]*average average.c~$ls[h-s]*.chello.c sort.c sum.c~$*.cは.cで終わる文字列。（拡張子で區(qū)別すると、特定種類(lèi)のファイルだけを指定できる。）[ab]*はaかbで始まる文字列。（長(zhǎng)いファイル名を一括して扱える。）[h-s]*.cはhからsのどれかの文字で始まり、.cで終わる文字列。（組み合わせてファイルを絞り込める。）第36頁(yè)，共42頁(yè)，2023年，2月20日，星期一371－５．拡張NFADFA、NFA共に、入力記號(hào)１文字に対して、１つの遷移を行っていた。この制限を緩和した計(jì)算機(jī)モデルが考えられる。拡張NFAとは、遷移のラベルとして正規(guī)表現(xiàn)を許すNFAである。拡張NFA：GeneralizedNon-deterministicfiniteAutomaton

なのでGNFAと略する。第37頁(yè)，共42頁(yè)，2023年，2月20日，星期一38GNFAの形式的定義GNFAは、の５項(xiàng)組で與えられる。ここで、１．は有限集合で、狀態(tài)を表す。２．は有限集合で