理学类情报数理学.pptVIP

*とに対して、入力1011の状態遷移を木によって示し、受理か不受理かを確認せよ。練習第30页，共42页，星期日，2025年，2月5日第1页，共42页，星期日，2025年，2月5日*履修にあたって2007年度大学院奇数セメスター（前期）開講K336→大学院棟D４１６（次回から）教室：時限：火曜日３時限（12:50－14:20）担当 草苅良至第2页，共42页，星期日，2025年，2月5日*講義予定○計算機のいろいろな理論モデル○計算の限界○問題の難しさ○現実問題と計算言語理論計算量理論アルゴリズム論第3页，共42页，星期日，2025年，2月5日*参考書M.R.GareyandD.S.Johnson,ComputersAndIntractability:AguidetotheTheoryofNP-Completeness,Freeman,1979,ISBN:0-7167-1045-5岩間一雄、「アルゴリズム理論入門」昭晃堂、2001、ISBN：4-7856-3125-2ホップクロフト、ウルマン、「オートマトン?言語理論?計算論I,II」サイエンス社、1984,ISBN:4-7819-0374-6,4-7819-0432-7M.Sipser著、「計算理論の基礎」、共立出版、1997,ISBN:4-320-02948-8岩間一雄、「オートマトン?言語と計算理論」コロナ社、2003、ISBN：4-339-01821-XV.V.ヴィジラーニ著、浅野孝夫訳、「近似アルゴリズム」、シュプリンガー?フェアラーク東京、２００２、ISBN:4-431-70991-6第4页，共42页，星期日，2025年，2月5日*１．オートマトンと正規表現第5页，共42页，星期日，2025年，2月5日*1－1．有限オートマトンメモリがほとんどなく、「はい」と「いいえ」しか答えられない計算機を考える。101110入力テープ自動機械ランプ入力テープを”一度だけ“走査したあと、「はい」ならランプ点灯「いいえ」ならランプ消灯。このような自動機械を(有限）オートマトンという。第6页，共42页，星期日，2025年，2月5日*テープ有限制御部ヘッド01有限オートマトンの概略入力テープ テープに書ける文字オートマトンを定める要素有限制御部 内部状態 初期状態 状態変化 受理かどうかの判断第7页，共42页，星期日，2025年，2月5日*有限オートマトンの数学的定義有限オートマトンは、の５項組で与えられる。ここで、１．は有限集合で、状態を表す。２．は有限集合で、入力記号の集合を表す。３．はからへの写像（）で、状態遷移を表す。を状態遷移関数という。４．は、初期状態を表す。５．は受理状態の集合を表す。とする。第8页，共42页，星期日，2025年，2月5日*有限オートマトンの図式表現（状態遷移図）有限オートマトンは、状態遷移図で表現できる。オートマトン例0011このオートマトンの形式的定義（数学的定義）は、であり、は次の状態遷移表により定義される。第9页，共42页，星期日，2025年，2月5日*練習次のオートマトンの数学的表現を与えよ。011001第10页，共42页，星期日，2025年，2月5日*1－2．言語計算機が扱える対象は、{0,1}で表された数と考えがちである。しかし、{0,1}の並びを一種の言語とみなすこともできる。任意の有限集合をアルファベットという。アルファベットの要素を文字という。アルファベットの任意の列を文字列という。文字列の集合を、（アルファベット上の）言語という。ここで、計算機で扱える対象について再考する。以下では、言語の数学的定義を与える。第11页，共42页，星期日，2025年，2月5日*言語の例1アルファベット例：上の文字列例：bookaaaab上の言語例：第12页，共42页，星期日，2025年，2月5日*言語の例2アルファベット例：上の文字列例：000001100010001111110111上の言語例：第13页，共42页，星期日，20