形式言語とオートマトン
| 科目区分 | 専門教育科目（情報） | 対象学年(以上) | 2年 |
|---|---|---|---|
| 科目名称 | 形式言語とオートマトン | 単位数 | 2.00単位 |
| 講義題目 | 形式言語とオートマトン | 曜日・時限 | 木曜2限 |
| 担当教員 | 辻 孝吉 | 開講時期 | 2019年度後期 |
| 到達目標 | 離散数学Ⅰの内容をふまえ、情報を数学的に取り扱う際に必要となる基礎的な概念について理解することが出来る。特に、離散的情報を取り扱うための重要な数学モデルであるオートマトンとプログラミングの基礎理論である形式言語理論について理解することが出来る。 | ||
| 授業概要 | 情報科学を学ぶ上で必要な数学の概要を今までに習得した数学と結びつけて復習するとともに情報科学を学ぶ上で必要と思われる数理について解説する。具体的に新しく解説する内容としては、オートマトンと言語理論（順序機械、有限オートマトン、非決定性有限オートマトン、有限オートマトンと正規集合、正規表現等）の基礎的な部分について解説する。 特に、有限オートマトンの理解とともに、決定性・非決定性の違い、等価性、オートマトンと正規表現の関係、プッシュダウンオートマトンが理解できることを目指すと共に簡単な例題を解くことができるようにする。 |
||
| 授業計画 | 第1回 オートマトンと言語 第2回 順序機械 第3回 特別な順序機械 第4回 順序機械とオートマトン 第5回 有限オートマトンと識別 第6回 有限オートマトンの識別能力 第7回 非決定性有限オートマトン 第8回 ε 動作とオートマトン 第9回 中間まとめ 第10回 決定性有限オートマトンと非決定性有限オートマトン 第11回 有限オートマトンの簡単化 第12回 言語演算 第13回 正規表現 第14回 有限オートマトンの構成 第15回 全体のまとめ 定期試験 |
||
| 授業外学習 | 講義中指定した箇所の予習・復習や小テストの問題は完全に解けるように復習しておくこと。 | ||
| 履修上の注意 | 関連科目：離散数学Ⅰ、離散数学Ⅱ 受講要件：離散数学Ⅰを履修していること。 その他：毎回出欠確認を兼ねて10分程度の小テストを行う。 |
||
| 成績評価の方法 | 評価基準：有限オートマトン、決定性・非決定性の違い、等価性、オートマトンと正規表現の関係、プッシュダウンオートマトンを理解しているか。 評価方法：試験（80％）、レポート（10％）及び毎回行う小テスト等（10％）を総合して評価する。 |
||
| 教科書 | 冨田・横森：オートマトン・言語理論、森北出版, 1992 | ||
| 参考書 | 福村・稲垣：オートマトン・形式言語理論と計算論、岩波書店 John E. Hopcroft,Rajeev Motiwani and Jeffrey D.Ullman:Introduction to Automata Theory, Languages,and Computation 2nd edition,Addison Wesley,2001 その他、講義ノート、参考書等は適宜ホームページなどで紹介する。 |
||