オートマトン·言語理論
Automata and Formal Languages
教授・北 研二
2単位
目的
情報工学，計算機科学一般において最も中心的な概念であるオートマトンと言語理論について講義し，レポート，小テストを実施して，理論と考え方を習得させる.
概要
言語の有限的記述の概念から始め，言語の基本的な記述機構としてオートマトン及び形式文法を導入する. また，文法とオートマトンの関係についても説明する. 講義では，特に基本的で重要な有限オートマトンと正則文法および文脈自由文法について詳しく述べる.
キーワード
有限オートマトン，形式言語，正則表現
先行科目
関連科目
要件
集合に関する基本的な知識(たとえば「離散数学とグラフ理論1」) を前提とする．
目標
| 1. | 形式言語理論の考え方，特に有限オートマトンや正則表現を用いた言語 の記述について理解する． |
| 2. | 有限オートマトンの等価性，非決定性オートマトンから決定性オートマトンへの 変換，オートマトンと正則表現の間の変換などの計算ができる． |
計画
| 1. | 基礎的な数学的準備，言語とその表現 |
| 2. | 順序機械 |
| 3. | 有限オートマトンと正則言語 |
| 4. | 有限オートマトンの等価性 |
| 5. | 有限オートマトンの最簡形 |
| 6. | 非決定性有限オートマトン |
| 7. | 部分集合構成法 |
| 8. | ϵ動作を持つ有限オートマトン |
| 9. | 言語演算 |
| 10. | 正則表現1 |
| 11. | 正則表現2 |
| 12. | 言語族の閉包性 |
| 13. | 形式文法1 |
| 14. | 形式文法2 |
| 15. | 演習 |
| 16. | 定期試験 |
評価
受講姿勢，レポートの提出状況と内容，小テスト及び最終試験の成績を総合して行う.
対象学生
開講コース学生のみ履修可能
教科書
富田悦次·横森 貴 著「オートマトン·言語理論」森北出版
参考資料
ホップクロフト·ウルマン 著「オートマトン·言語理論·計算論I」サイエンス社
連絡先
北(Dr503, 088-656-7496, kita@is.tokushima-u.ac(no-spam).jp)
- オフィスアワー: 火曜日 12:50 - 14:20
備考
| 1. | 毎回の予習·復習を欠かさず行うこと. 随時，レポート及び小テストを実施する. |
| 2. | 成績評価に対する平常点と試験の比率は4:6とする. 平常点には受講姿勢，レポートの提出状況と内容を含み，試験には小テスト及び最終試験の成績を含む. |