計算理論は，情報科学において多くの重要な方法論と結果をもたらした。例えば，有限オートマトンに関する基礎的な事柄は，情報科学の多くの分野で必須の知識となっている。 　本講義ではまず，重要な言語クラスである正規言語と文脈自由言語に話題を絞り，形式言語理論のエッセンスを解説する。 次に「計算機で解けない問題があるのだろうか」といった，計算機の能力の限界に関する疑問に答えていく。 　最後に，さまざまな計算モデルの関係を表すチョムスキー階層について簡単に解説する。 　　１. 正規言語 　　　 ・有限オートマトン（定義，決定性モデルと非決定性モデルの等価性） 　　　 ・正規表現（定義， 有限オートマトンとの等価性） 　　　 ・有限オートマトンの簡単化 　　２. 文脈自由言語 　　　 ・文脈自由文法（定義， 簡単化， チョムスキー標準形） 　　　 ・文脈自由言語の性質 　　　 （言語演算に対する閉包性， パンピングレンマ， 認識アルゴリズム） 　　３. 計算可能性 　　　 ・チューリング機械（定義， 能力を限定／拡張したモデル） 　　　 ・決定不能性（対角線論法， 還元による証明法） 　　４. チョムスキー階層 　　　 ・正規文法と有限オートマトン 　　　 ・文脈規定文法と線形拘束オートマトン 　　　 ・0型文法とチューリング機械

　

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

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

(必ずしも先修条件ではない) アルゴリズムとデータ構造（アルゴリズム概論 ）　 ブール代数（計算機構造概論）

試験により成績を評価する。