科目分野	理工学部
選必区分	選択
担当教員 ［ローマ字表記］	吉田　稔　[Minoru Yoshida]
授業形態	講義

授業の目的

情報工学，計算機科学一般において最も中心的な概念であるオートマトンと言語理論について講義し，レポート，小テストを実施して，理論と考え方を習得させる.

授業概要

言語の有限的記述の概念から始め，言語の基本的な記述機構としてオートマトン及び形式文法を導入する. また，文法とオートマトンの関係についても説明する. 講義では，特に基本的で重要な有限オートマトンと正則文法および文脈自由文法について詳しく述べる.

到達目標

1. 有限オートマトンや正則表現を用いて簡単な言語を記述することができる．


2. 有限オートマトンの等価性，非決定性オートマトンから決定性オートマトンへの変換，オートマトンと正則表現の間の変換などの計算ができる．

授業計画

1. 基礎的な数学的準備，言語とその表現


2. 順序機械


3. 有限オートマトンと正則言語


4. 有限オートマトンの等価性


5. 有限オートマトンの最簡形


6. 非決定性有限オートマトン


7. 部分集合構成法


8. ε動作を持つ有限オートマトン


9. 言語演算


10. 正規表現1（正規表現の定義）


11. 正規表現2（正規表現への変換）


12. 言語族の閉包性


13. 形式文法1（形式文法の定義）


14. 形式文法2（正規文法）


15. 演習


16. 定期試験

教科書

オートマトン・言語理論　第２版／富田悦次，横森貴：森北出版，2013.12, ISBN:9784627805521

キーワード

有限オートマトン, 形式言語, 正則表現