計算理論 I
Theory of Computation I

---

講義内容

　計算理論は，情報科学において多くの重要な方法論と結果をもたらした。例えば，有限オートマトンに関する基礎的な事柄は，情報科学の多くの分野で必須の知識となっている。
　本講義ではまず，重要な言語クラスである正規言語と文脈自由言語に話題を絞り，形式言語理論のエッセンスを解説する。 次に「計算機で解けない問題があるのだろうか」といった，計算機の能力の限界に関する疑問に答えていく。
　最後に，さまざまな計算モデルの関係を表すチョムスキー階層について簡単に解説する。

　　１. 正規言語
　　 ・有限オートマトン（定義， 決定性モデルと非決定性モデルの等価性）
　　　 ・正規表現（定義， 有限オートマトンとの等価性）
　　　 ・有限オートマトンの簡単化
　　２. 文脈自由言語
　　　 ・文脈自由文法（定義， 簡単化， チョムスキー標準形）
　　　 ・文脈自由言語の性質
　　　 （言語演算に対する閉包性， パンピングレンマ， 認識アルゴリズム）
　　３. 計算可能性
　　　 ・チューリング機械（定義， 能力を限定／拡張したモデル）
　　　 ・決定不能性（対角線論法， 還元による証明法）
　　４. チョムスキー階層
　　　 ・正規文法と有限オートマトン
　　　 ・文脈規定文法と線形拘束オートマトン
　　　 ・0型文法とチューリング機械

　
教科書

　　J.ホップクロフト・J.ウルマン著，野崎・高橋・町田・山崎訳 ：
　　　　オートマトン 言語理論 計算論 I，サイエンス社，1984.

参考書

　　１. J.E.Hopcroft and J.D.Ullman : Introduction to Automata Theory，Languages，
　　　　and Computation，Addison-Wesley，1979
　　　　（本講義の教科書の原典）
　　２. 富田悦次・横森貴著 : オートマトン・言語理論， 森北出版
　　　　（基本となる概念を丁寧に説明したテキスト）

前提とする知識(必ずしも先修条件ではない)

　　アルゴリズムとデータ構造（アルゴリズム概論 ）　
　　ブール代数（計算機構造概論）