2011年度 工学部 知能情報工学科 昼間コース — [選択] 3年(前期)

オートマトン·言語理論

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時間の授業時間毎に2時間の予習と2時間の復習をし たうえで授業を受けることが,授業の理解と単位取得のために必要である.
2.授業計画1∼14は,各講義の最後に行なわれる演習および最終試験により達成 度評価を行なう.