計算理論 I
Theory of Computation I
講義内容
計算理論は， 情報科学において多くの重要な方法論と結果をもたらした。例
えば， 有限オートマトンに関する基礎的な事柄は， 情報科学の多くの分野で
必須の知識となっている。
本講義ではまず、重要な言語クラスである正規言語と文脈自由言語に話題を絞
り，形式言語理論のエッセンスを解説する。 次に， 「計算機で解けない問題
があるのだろうか」といった，計算機の限界に関する疑問に答えていく。
最後に，さまざまな計算モデルの関係を表すチョムスキー階層について解説す
る。
- 正規言語
- 有限オートマトン（定義， 決定性モデルと非決定性モデルの等価性）
- 正規表現（定義， 有限オートマトンとの等価性）
- 有限オートマトンの簡単化
- 文脈自由言語
- 文脈自由文法（定義， 簡単化， チョムスキー標準形）
- 文脈自由言語の性質
（言語演算に対する閉包性， パンピングレンマ， 認識アルゴリズム）
- 計算可能性
- チューリング機械（定義， 能力を限定／拡張したモデル）
- 決定不能性（対角線論法， 還元による証明法）
- チョムスキー階層
- 正規文法と有限オートマトン
- 文脈規定文法と線形拘束オートマトン
- 0型文法とチューリング機械
教科書
J.ホップクロフト・J.ウルマン著，野崎・高橋・町田・山崎訳 ：
オートマトン 言語理論 計算論 I，II，サイエンス社，1984，1986.
（II巻は第II期「ソフトウェア基礎論」でも教科書として使います）
参考書
- J.E.Hopcroft and J.D.Ullman : Introduction to Automata Theory,
Languages, and Computation, Addison-Wesley, 1979
（本講義の教科書の原典）
- 富田悦次・横森貴著 : オートマトン・言語理論， 森北出版
（基本となる概念を丁寧に説明したテキスト）
前提とする知識(必ずしも先修条件ではない)
- アルゴリズムとデータ構造（アルゴリズム概論 ）
- ブール代数（計算機構造概論）