理學(xué)類情報(bào)數(shù)理學(xué)

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

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

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

文字列

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

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

とを例にして、DFAとNFAの狀態(tài)遷移を調(diào)べる。DFAとNFAの狀態(tài)遷移入力：とする。入力第二十八頁，共四十二頁，2022年，8月28日29ＮＦＡの受理NFAの受理とは、入力系列を受理する遷移の系列が存在することである。受理系列第二十九頁，共四十二頁，2022年，8月28日30

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

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

なのでGNFAと略する。第三十七頁，共四十二頁，2022年，8月28日38GNFAの形式的定義GNFAは、の５項(xiàng)組で與えられる。ここで、１．は有限集合で、狀態(tài)を表す。２．は有限集合で、