理学类情报数理学优秀PPT.ppt
理学类情报数理学你现在浏览的是第一页，共42页2履修2007年度大学院奇数（前期）開講K336大学院棟D（次回）教室：時限：火曜日時限（12:5014:20）担当草苅良至你现在浏览的是第二页，共42页3講義予定計算機理論計算限界問題難現実問題計算言語理論計算量理論論你现在浏览的是第三页，共42页4参考書M.R.Garey and D.S.Johnson,Computers And Intractability:A guide to the Theoryof NP-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你现在浏览的是第四页，共42页5正規表現你现在浏览的是第五页，共42页611有限、答計算機考。101110入力自動機械入力”一度“走査、点灯消灯。自動機械(有限）。你现在浏览的是第六页，共42页7有限制御部01有限概略入力書文字定要素有限制御部内部状態初期状態状態変化受理判断你现在浏览的是第七页，共42页8有限数学的定義有限、項組与。、有限集合、状態表。有限集合、入力記号集合表。写像（）、状態遷移表。状態遷移関数。、初期状態表。受理状態集合表。你现在浏览的是第八页，共42页9有限図式表現（状態遷移図）有限、状態遷移図表現。例0011形式的定義（数学的定義）、次状態遷移表定義。你现在浏览的是第九页，共42页10練習次数学的表現与。011001你现在浏览的是第十页，共42页1112言語計算機扱対象、0,1表数考。、0,1並一種言語。任意有限集合。要素文字。任意列文字列。文字列集合、（上）言語。、計算機扱対象再考。以下、言語数学的定義与。你现在浏览的是第十一页，共42页12言語例1例：上文字列例：bookaaaab上言語例：你现在浏览的是第十二页，共42页13言語例2例：上文字列例：000001100010001111110111上言語例：你现在浏览的是第十三页，共42页14言語関諸概念、文字列関諸概念定義与。文字列w含文字数、文字列w長、文字列長：記号表。空列：長0文字列空列、記号 表。連結：文字列 後文字列 繋文字列 連結次記号表。你现在浏览的是第十四页，共42页15例上文字列考。、次式成立。文字列連結演算、交換不可你现在浏览的是第十五页，共42页16言語関諸概念、言語関諸概念定義与。言語連結（連結演算）：言語閉包(演算）：言語和集合(和集合演算）：言語。你现在浏览的是第十六页，共42页17例上言語考。、次式成立。你现在浏览的是第十七页，共42页18要素無言語空列言語要素無言語空列言語異。、。你现在浏览的是第十八页，共42页19言語受理入力集合、入力記号 上言語。例0011 受理言語 書。例、。你现在浏览的是第十九页，共42页20練習次言語受理 作成。、状態遷移図、形式的定義両方示事。你现在浏览的是第二十页，共42页2113非決定性(有限）、入力記号、状態遷移一意定。制限緩和計算機考。非決定性、同入力対複数遷移”。対、同入力対、一遷移”決定性。你现在浏览的是第二十一页，共42页22略記決定性、英語、Deterministic Finite Automaton、DFA略記。非決定性、英語、Non-determinisc Finite Automaton、NFA略記。你现在浏览的是第二十二页，共42页23NFA形式的定義非決定性有限、項組与。、有限集合、状態表。有限集合、入力記号集合表。写像 、状態遷移表。状態遷移関数。、初期状態表。受理状態集合表。你现在浏览的是第二十三页，共42页24NFA状態遷移図0,110,10,1形式的定義（数学的定義）、次状態遷移表定義。你现在浏览的是第二十四页，共42页25 受理言語 、。実、非決定性受理言語同言語受理決定性常存在。自体能力差。、証明。你现在浏览的是第二十五页，共42页26言語受理DFA 示。0110001111111000你现在浏览的是第二十六页，共42页27練習言語受理非決定性決定性示。上你现在浏览的是第二十七页，共42页28 例、DFANFA状態遷移調。DFANFA状態遷移入力：。入力你现在浏览的是第二十八页，共42页29受理NFA受理、入力系列受理遷移系列存在。受理系列你现在浏览的是第二十九页，共42页30 対、入力1011状態遷移木示、受理不受理確認。練習你现在浏览的是第三十页，共42页311正規表現(正則表現）DFA受理言語対、正規表現呼別表現法知。上正規表現、下記帰納的定義。、表集合、空集合。、表集合、。各元 対、正規表現、表集合、。言語 言語 表正規表現 、正規表現、表。正規表現形式的定義你现在浏览的是第三十一页，共42页32正規演算優先順位正規表現演算記号優先順位、括弧省略。通常、上優先順位考、不必要括弧省略。你现在浏览的是第三十二页，共42页33例 上正規表現考。你现在浏览的是第三十三页，共42页34練習、次正規表現表言語含文字列示、直感的意味述。（）（）（）（）（）你现在浏览的是第三十四页，共42页35正規表現応用UNIX、正規表現引数指定。、UNIX正規表現、UNIX独特注意。：任意文字列表。：一文字以上文字列。：文字：文字你现在浏览的是第三十五页，共42页36例$ls*.caverage.chello.csort.csum.c$ls ab*averageaverage.c$ls h-s*.chello.csort.csum.c$*.c.c終文字列。（拡張子区別、特定種類指定。）ab*ab始文字列。（長名一括扱。）h-s*.chs文字始、.c終文字列。（組合絞込。）你现在浏览的是第三十六页，共42页371拡張NFADFA、NFA共、入力記号文字対、遷移行。制限緩和計算機考。拡張NFA、遷移正規表現許NFA。拡張NFA：Generalized Non-deterministic finite Automaton GNFA略。你现在浏览的是第三十七页，共42页38GNFA形式的定義GNFA、項組与。、有限集合、状態表。有限集合、入力記号集合表。3.写像 、状態遷移表。状態遷移関数。、上正規表現集合（上正規言語）表。、初期状態表。受理状態表。你现在浏览的是第三十八页，共42页39GNFA状態遷移図1形式的定義（数学的定義）、次状態遷移表定義。你现在浏览的是第三十九页，共42页401GNFA関注意初期状態、他状態遷移。受理状態、他状態遷移。入矢印（）無。出行（）無。初期状態、受理状態。特、受理状態注意。你现在浏览的是第四十页，共42页41練習言語上受理状態拡張NFA状態遷移図、形式的定義両方示。你现在浏览的是第四十一页，共42页更多资源初一语文初一英语初一数学初一政治初一历史初一地理初一生物你现在浏览的是第四十二页，共42页
