シラバス

授業科目名	形式言語とオートマトン
	履修期 秋   2単位   履修基準年度 2年
担当者	岡留　剛（OKADOME TAKESHI）

授業目的 / Course Objectives

言語とそれを生成・受理する「機械」の数学として，文と呼ばれる記号列を生成する規則（文法）の構造と、その文法で生成された記号列の集合である言語を識別するシステム「オートマトン」の構造との間の対応関係と、言語に関するChomskyの階層について講義する。本講義内容は情報科学分野の常識の一つであり，Webページの解析やDNAの解析にと広く使われている．また，例えばロボットなどの人工物に言葉をしゃべらせる・理解させるための基本である．本講義では，Webページの解析に多用される正規表現についてJavaによる具体的表記も講義し、実践で役立つ知識を身につける。

到達目標 / Attainment Objectives

授業時間外の学習 (準備学習等について) / Study Required Outside of Class (Preparation etc.)

コンピュータ言語に関係する。また、コンパイラの授業については本講義内容は必須である。

授業計画 / Class Overall Plan

第1週．数学的準備 第2週．有限状態オートマトンとそれが受理する言語 第3週．非決定性有限状態オートマトン 第4週．ε動作を持つ有限状態オートマトンと正規表現 第5週．小演習1 第6週．状態最小化とポンプの補題 第7週．形式言語：正規言語と有限状態オートマトン 第8週．決定性プッシュダウンオートマトン 第9週．非決定性プッシュダウンオートマトンと文脈自由言語 第10週．小演習2 第11週．チューリングマシンと線形拘束オートマトン 第12週．言語のクラスとマシンのクラス：Chomskyの階層 第13週．決定不可能性：チューリングマシンの停止問題 第14週．総合演習

教科書 / Textbook(s)

参考文献 References Books

J. ホップクロフト・R. モトワニ・J. ウルマン『オートマトン 言語理論 計算論I・II 第２版』（サイエンス社, 2003） M. シプサー『計算理論の基礎 [原著第2版]』 1, 2 （共立出版，2008)

授業方法 / Method of Instruction

講義形式

学生による授業評価の方法 / Course Evaluation by Students

全学統一方式による．

成績評価 / Evaluation Criteria/Method

定期試験(Final examination) 小演習や総合演習の結果，また，通常授業における質疑応答の内容も成績に加味することもある．

備考 / Note

検索キーワード / Keywords

形式言語、オートマトン、形式文法