1 言語とその表現
1-1 アルファベットと言語
1-2 手続とアルゴリズム
1-3 言語の表現
1-4 演習問題
2 文法
2-1 動機
2-2 文法の形式的概念
2-3 文法の型
2-4 空文
2-5 文脈依存文法の帰納性
2-6 文脈自由文法における導出の木
2-7 演習問題
3 有限オートマトンと正規文法
3-1 有限オートマトン
3-2 同値関係と有限オートマトン
3-3 非決定性有限オートマトン
3-4 有限オートマトンと3型文法
3-5 3型文法の性質
3-6 有限オートマトンについての決定可能な問題
3-7 2方向有限オートマトン
3-8 演習問題
4 文脈自由文法
4-1 文脈自由文法の簡約化
4-2 Chomsky標準形
4-3 Greibach標準形
4-4 有限性問題の決定可能性と“uvwxy定理”
4-5 自己埋めこみ性
4-6 文脈自由文法のε-規則
4-7 特別な型の文脈自由言語と文脈自由文法
4-8 演習問題
5 プッシュダウン・オートマトン
5-1 pd-オートマトンとは
5-2 pd-オートマトンの定義
5-3 非決定性pd-オートマトンと文脈自由言語
5-4 演習問題
6 Turing機械
6-1 Turing機械
6-2 Turing機械の定義と表示法
6-3 Turing機械の構成技法
6-4 手続きとしてのTuring機械
6-5 Turing機械の諸変形
6-6 基本型に等価な制限されたTuring機械
6-7 演習問題
7 Turing機械：停止問題，0型言語
7-1 概説
7-2 万能Turing機械
7-3 停止問題の決定不能性
7-4 帰納的集合のクラス
7-5 Turing機械と0型文法
7-6 演習問題
8 線型有界オートマトンと文脈依存言語
8-1 序論
8-2 線型有界オートマトンと文脈依存言語の関係
8-3 文脈依存言語は帰納的集合の部分クラスである
8-4 演習問題
9 言語の演算
9-1 序論
9-2 基本演算のもとでの閉包性
9-3 写像のもとでの閉包性
9-4 演習問題
10 時間限定Turing機械およびテープ限定Turing機械
10-1 序論
10-2 諸定義
10-3 「加速定理」および「テープ節約定理」
10-4 テープ1本のTuring機械と通過列
10-5 テープ計算量の下界
10-6 テープ計算量および時間計算量の階層
10-7 演習問題
11 文脈自由言語の認識に要する時間とテープ量の限界
11-1 序論
11-2 文脈自由言語の認識に要する時間
11-3 文脈自由言語の認識に要するテープ量
11-4 演習問題
12 決定性プッシュダウン・オートマトン
12-1 序論
12-2 決定性言語の補集合
12-3 決定性言語の性質
12-4 非決定性文脈自由言語
12-5 LR(k)文法
12-6 演習問題
13 スタックオートマトン
13-1 定義
13-2 スタックオートマトンの変型
13-3 2方向スタックオートマトンの能力
13-4 1方向スタックオートマトンの能力
13-5 スタックオートマトンの帰属性
13-6 閉包の性質
13-7 演習問題
14 決定可能性
14-1 決定可能な問題とそうでない問題
14-2 Postの対応問題
14-3 文脈依存言語に関する問題
14-4 文脈自由言語の決定不能問題\r
14-5 文脈自由言語の曖昧さ
14-6 決定性文脈自由言語に関する決定不能問題\r
14-7 正規，LR(k)，文脈自由，文脈依存，0型の各文法に対する決定問題の結果の要約
14-8 演習問題
1-1 アルファベットと言語
1-2 手続とアルゴリズム
1-3 言語の表現
1-4 演習問題
2 文法
2-1 動機
2-2 文法の形式的概念
2-3 文法の型
2-4 空文
2-5 文脈依存文法の帰納性
2-6 文脈自由文法における導出の木
2-7 演習問題
3 有限オートマトンと正規文法
3-1 有限オートマトン
3-2 同値関係と有限オートマトン
3-3 非決定性有限オートマトン
3-4 有限オートマトンと3型文法
3-5 3型文法の性質
3-6 有限オートマトンについての決定可能な問題
3-7 2方向有限オートマトン
3-8 演習問題
4 文脈自由文法
4-1 文脈自由文法の簡約化
4-2 Chomsky標準形
4-3 Greibach標準形
4-4 有限性問題の決定可能性と“uvwxy定理”
4-5 自己埋めこみ性
4-6 文脈自由文法のε-規則
4-7 特別な型の文脈自由言語と文脈自由文法
4-8 演習問題
5 プッシュダウン・オートマトン
5-1 pd-オートマトンとは
5-2 pd-オートマトンの定義
5-3 非決定性pd-オートマトンと文脈自由言語
5-4 演習問題
6 Turing機械
6-1 Turing機械
6-2 Turing機械の定義と表示法
6-3 Turing機械の構成技法
6-4 手続きとしてのTuring機械
6-5 Turing機械の諸変形
6-6 基本型に等価な制限されたTuring機械
6-7 演習問題
7 Turing機械：停止問題，0型言語
7-1 概説
7-2 万能Turing機械
7-3 停止問題の決定不能性
7-4 帰納的集合のクラス
7-5 Turing機械と0型文法
7-6 演習問題
8 線型有界オートマトンと文脈依存言語
8-1 序論
8-2 線型有界オートマトンと文脈依存言語の関係
8-3 文脈依存言語は帰納的集合の部分クラスである
8-4 演習問題
9 言語の演算
9-1 序論
9-2 基本演算のもとでの閉包性
9-3 写像のもとでの閉包性
9-4 演習問題
10 時間限定Turing機械およびテープ限定Turing機械
10-1 序論
10-2 諸定義
10-3 「加速定理」および「テープ節約定理」
10-4 テープ1本のTuring機械と通過列
10-5 テープ計算量の下界
10-6 テープ計算量および時間計算量の階層
10-7 演習問題
11 文脈自由言語の認識に要する時間とテープ量の限界
11-1 序論
11-2 文脈自由言語の認識に要する時間
11-3 文脈自由言語の認識に要するテープ量
11-4 演習問題
12 決定性プッシュダウン・オートマトン
12-1 序論
12-2 決定性言語の補集合
12-3 決定性言語の性質
12-4 非決定性文脈自由言語
12-5 LR(k)文法
12-6 演習問題
13 スタックオートマトン
13-1 定義
13-2 スタックオートマトンの変型
13-3 2方向スタックオートマトンの能力
13-4 1方向スタックオートマトンの能力
13-5 スタックオートマトンの帰属性
13-6 閉包の性質
13-7 演習問題
14 決定可能性
14-1 決定可能な問題とそうでない問題
14-2 Postの対応問題
14-3 文脈依存言語に関する問題
14-4 文脈自由言語の決定不能問題\r
14-5 文脈自由言語の曖昧さ
14-6 決定性文脈自由言語に関する決定不能問題\r
14-7 正規，LR(k)，文脈自由，文脈依存，0型の各文法に対する決定問題の結果の要約
14-8 演習問題