言語理論とオートマトン[22C5041]

科目名
Course Title
言語理論とオートマトン[22C5041]
Language Theory and Automata
授業言語
Language
Japanese
科目区分・科目種 情報科学科 クラス 情報科学科
CCBM キャリアデザイン  
単位数 2.0単位 履修年次 34

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

受講条件・その他注意
授業スライドを用いた講義を行う.スライド上には演習問題をいくつか用意しているが,解答は提供していない.演習問題の答案を提示すれば採点・講評を添えて返事を行うが,これらは必須事項ではない.オンライン併用の講義を行う予定である.

授業の形態
講義,一部対面授業あり,実施方法検討中

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

ALH区分
通常授業として実施(11・12限等)

評価方法・評価割合
期末試験=40%,小論文(レポート)=20%×3回,ALH(アクティブ・ラーニング・アワー)=40%相当

主題と目標
理論計算機科学から計算機科学の工学的応用まで様々な分野を支える重要な概念である形式言語についての講義を行う.
本講義では特に正則言語/正則表現と文脈自由文法/文脈自由言語を確認し、それらと同等な計算モデルを学習する.

授業計画
第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回
文脈自由文法では記述できない言語

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

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

学生の問い合わせ先
メール:a-nagao@is.ocha.ac.jp
居室:理学部3号館401室