形式言語理論

1 基本的定義と記法 1.1 関係と部分関数 1.2 記号列，アルファベット，言語 2 有限オートマトンと正則言語 2.1 有限オートマトン序章 2.2 有限オートマトンの定義 2.3 非決定性有限オートマトンと決定性有限オートマトンの等価性 2.4 ε動作付非決定性有限オートマトン 2.5 正則言語のPumping Lemma 2.6 正則表現 2.7 有限オートマトンと正則表現 2.8 正則言語の性質 2.9 ブール行列による有限オートマトンの表現 2.10 最小オートマトン 2.10.1 Myhill-Nerode の定理 2.10.2 状態数の最小化 2.11 順序機械 2.12 有限オートマトンについてのアルゴリズム 3 文脈自由文法 3.1 定義と例 3.1.1 導出木 3.2 文法の簡素化 3.2.1 無駄な変数の除去 3.2.2 A → εの形の生成規則 3.2.3 A → B の形の生成規則 3.3 Chomsky 標準形 3.4 文脈自由言語の性質 3.4.1 Pumping Lemma 3.4.2 Ogdenの定理 3.5 文脈自由文法の所属性判定問題 3.6 有限オートマトンと正則文法 4 Turing 機械 4.1 定義 4.2 Turing 機械による関数の計算 4.3 Turing 機械の変種 4.3.1 非決定性Turing 機械 4.3.2 マルチテープTuring 機械 4.3.3 両方向に無限の長さをもつテープ 4.3.4 オフラインTuring 機械 4.3.5 多次元テープTuring 機械 4.3.6 その他の計算のモデル 4.4 Church のテーゼ 4.5 帰納的可算集合と帰納的集合 4.6 決定不能な問題

講義を中心に行う。

レポート提出状況と期末試験の成績で評価を行う。

講義の中で配布する。

●John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, (3rd Edition), Addison-Wesley, 2006. ●有川節夫，宮野悟，「オートマトンと計算可能性」（第１章，２章，３章），培風館，1986.

特になし

※初回１回はオンラインとなります。