オートマトン理論 (藤原　暁宏)

  科目名: オートマトン理論 (01)　Automata Theory

  担当教員: 藤原　暁宏 (大学院情報工学研究院電子情報工学研究系)　fujiwara@cse.kyutech.ac.jp

            情報科目 選択必修科目 2単位

            2年 後期 月曜5限目  1305講義室

授業の概要

“オートマトン” は、現在の計算機に共通する計算の原理の数学的モデルであり、”形式言語”は、プログラミング言語、自然言語処理における基礎分野である。この講義では、この２つについて体系的に講義するとともに、この２つを用いて定義される計算能力のクラスについても教授する。（関連する学習教育目標：C-2-1）

カリキュラムにおけるこの授業の位置付け

計算機科学の基礎理論分野であり、今後の情報系理論科目を学ぶ基礎となる。「離散数学」の単位を履修していることを前提とする。

授業項目 (授業計画)

(1)　オートマトンと形式言語の基礎

(2)　順序機械（定義、状態遷移図、状態遷移表、簡単化）

(3)　有限オートマトンの定義とオートマトンの等価性

(4)　非決定性有限オートマトンとε-動作を持つ有限オートマトン

(5)　正規言語、正規表現

(6)　例題演習(1)

(7)　中間試験

(8)　形式文法の定義、及び、正規文法と有限オートマトンの関係

(9)　文脈自由文法、文脈自由言語

(10)　プッシュダウンオートマトン

(11)　チューリング機械

(12)　計算可能性、決定問題

(13)　コンパイラの基礎と構文解析

(14)　例題演習(2)

(15)　期末試験

授業の進め方

配布資料を中心とした講義を行なう。また、各講義の最後に演習課題を課すとともに、中間試験、期末試験を各１回実施する。

授業の達成目標 (学習・教育目標との関連)

この講義では、電子情報法工学科の学習・教育目標(C-2-1)に掲げられている「ハードウェアとソフトウェアの関係から動作原理を理解している。」という目標を達成するため、計算機の動作の基礎概念であるオートマトンを理解させるとともに、プログラミング言語や人工知能の基礎である形式言語の基礎についても修得させる。これにより、以下の内容の基本的事項を理解し、それに関する基本的問題を解くことができることを目標とする。

(1)　有限オートマトンの定義，動作を理解し、簡単な有限オートマトンを設計できる。

(2)　等価な有限オートマトンへの変換方法を理解する。

(3)　形式言語の定義、言語生成方法、及び、簡単な形式言語の設計方法を理解する。

(4)　有限オートマトンと形式言語の等価性、及び、言語のクラス階層について理解する。

成績評価の基準および評価方法

毎回の演習課題(20％)により達成目標(1),(2),(3),(4)の達成度を段階的に評価する。また、達成目標の(1), (2)については中間試験(40％)において、達成目標の(3),(4)については期末試験(40％)において総合的に評価する。

キーワード

オートマトン、形式言語、チューリング機械、計算可能性

教科書

講義資料を毎回配付する。なお、この講義資料はWebにて閲覧可能である。

参考書

• 富田悦二、横森 貴: オートマトン・言語理論(基礎情報工学シリーズ5) (森北出版)
• 都倉信樹: オートマトンと形式言語 (昭晃堂)

備考