授業科目名 : 言語・オートマトン

科目コード 91040
配当学年 2年
開講年度・開講期 平成30年度・後期
曜時限 月曜・3時限
講義室 総合研究8号館講義室2
単位数 2
履修者制限
授業形態 講義
使用言語 日本語
担当教員    所属・職名・氏名 情報学研究科・教授・山本章博

授業の概要・目的

情報学の数理的基盤の一つである形式言語理論および、オートマトンからTuring機械に至る抽象的な計算機構について講述する。また、これらの応用についても適宜言及する。

成績評価の方法・観点及び達成度

小テストと定期試験の成績を総合して評価する。

到達目標

形式言語と計算機構の関係について,情報学的視点および数理的な視点の両方から理解する。

授業計画と内容

項目 回数 内容説明
イントロダクション 1 集合論、文字列の数学、形式言語
有限オートマトン 5 有限オートマトンの表現、最小化、正則表現と正則文法、、等価性、順序機械
文脈自由言語 4 文脈依存文法、文脈自由文法、Chomsky標準形、構文解析、Greibach標準形、プッシュダウンオートマトン
チューリング機械および関連する話題 3 Turing機械、万能性、帰納的集合、帰納的に可算な集合、決定可能性、言語の演算
言語の能力差 2 最後に言語階層全体のまとめを行う。講義の最後に学習到達度判定のための質疑を行う.

教科書

教科書は指定しないが,講義の進展に合わせて下記の参考書の少なくとも一つを熟読することを望む.

参考書等

Hopcroft, Motowani, Ullman, Introduction to Automata Theory, Languages, and Computation -3rd Edition- Peason, 2007
Hopcroft,Ullman, Motowani, オートマトン言語理論 計算論 [第2版] I および II(上記の第2版の邦訳) ,2003  
富田・横森,オートマトン・言語[第2版],森北出版,2013
岡留,例解図説 オートマトンと形式言語入門,森北出版,2015
有川(監修)西野・石坂(著) 形式言語の理論,丸善出版,1999

履修要件

数学における集合に関する初歩的知識を要する.

授業外学習(予習・復習)等

講義はスライド資料と板書の両方を用いて進める。各回に演習問題を解く時間を設ける予定である。スライド資料と演習問題は講義前にKULASISまたはPandAにアップロードしておくので、各自PC等にダウンロードしてから講義に臨むこと。なお、演習問題のための時間は十分ではないため、各自の復習を要する。

授業URL

その他(オフィスアワー等)