科目名 Course Title	言語理論とオートマトン［26C5041］ Language Theory and Automata
授業言語 Language	Japanese
科目区分・科目種	情報科学科	クラス	情報科学科
コンピテンシー	◎批判的思考力，○問題解決力	ｶﾗｰｺｰﾄﾞ
単位数	2.0単位	履修年次	3〜4年

担当教員	長尾　篤樹
学期	前期
曜日・時限・教室	金曜 3 〜 4 限 共3-409【情報科学講義室1】

受講条件・その他注意
授業スライドを用いた講義を行う．スライド上には演習問題をいくつか用意しているが，解答は提供していない．演習問題の答案を提示すれば採点・講評を添えて返事を行うが，これらは必須事項ではない． 講義は録画し、後日確認できるよう公開する予定である．

授業の形態
講義

教科書・参考文献
参考書：Michael Sipser著『Introduction to the Theory of Computation』ISBN:978-1133187790 参考書：Michael Sipser著『計算理論の基礎 [原著第2版] 1.オートマトンと言語』ISBN:978-4320122079（上述参考書の和訳版） いずれも購入の必要はない． 英語原著はPDFファイルがインターネット上に公開されている．

ＡＬＨ区分
ＡＬＨを実施しない

アクティブラーニングの技法
復習テスト，間違い探し

評価方法・評価割合
期末試験=40%，小論文（レポート）=20%×3回

主題と目標
理論計算機科学から計算機科学の工学的応用まで様々な分野を支える重要な概念である形式言語についての講義を行う． 本講義では特に正則言語/正則表現と文脈自由文法/文脈自由言語を確認し、それらと同等な計算モデルを学習する． 全15回の授業を予定し、各種レポートと期末試験を課す予定である。

授業計画
第1回	ガイダンス、「集合」について
第2回	決定有限オートマトン（Deterministic Finite Automaton: DFA）
第3回	決定性有限オートマトンと正規演算
第4回	非決定性有限オートマトン（Non-deterministic Finite Automaton: NFA）
第5回	DFAとNFAの等価性
第6回	正規演算の閉包性
第7回	正規表現とDFAの等価性
第8回	DFAでは認識できない言語
第9回	文脈自由文法（Context Free Grammar: CFG）
第10回	チョムスキー標準形
第11回	プッシュダウンオートマトン（Push Down Automaton: PDA）
第12回	CFGとPDAの等価性�@
第13回	CFGとPDAの等価性�A
第14回	文脈自由文法では記述できない言語
第15回	言語理論とオートマトンまとめ

時間外学習
授業スライドの予習，スライド上の演習問題への取り組みを期待する．また，参考書を各自で読み進めることでより深く広い理解を得られるため，こちらも推奨する．

学生へのメッセージ
言語理論は、コンピュータサイエンスの最も基礎的な理論のひとつで、いろいろな分野でその考え方が使われます。多少、抽象的な部分もありますが、わかりやすく説明していきたいと思っていますので、是非、しっかりと習得して下さい。

学生の問い合わせ先
基本的には情報科Slackの授業チャンネルやDMにて連絡を取ること． メール：a-nagao@is.ocha.ac.jp 居室：理学部3号館401室