1 言語とその表現 |
1.1 アルファベットと言語 1 |
1.2 手続とアルゴリズム 3 |
1.3 言語の表現 6 |
演習問題 8 |
2 文法 |
2.1 動機 9 |
2.2 文法の形式的概念 11 |
2.3 文法の型 15 |
2.4 空文 17 |
2.5 文脈依存文法の帰納性 19 |
2.6 文脈自由文法における導出の木 22 |
演習問題 28 |
3 有限オートマトンと正規文法 |
3.1 有限オートマトン 30 |
3.2 同値関係と有限オートマトン 32 |
3.3 非決定性有限オートマトン 35 |
3.4 有限オートマトンと3型文法 39 |
3.5 3型文法の性質 42 |
3.6 有限オートマトンについての決定可能な問題 47 |
3.7 2方向有限オートマトン 49 |
演習問題 54 |
4 文脈自由文法 |
4.1 文脈自由文法の簡約化 56 |
4.2 Chomsky標準形 61 |
4.3 Greibach標準形 63 |
4.4 有限性問題の決定可能性と"uvwxy定理" 69 |
4.5 自己埋めこみ性 73 |
4.6 文脈自由文法のε-規則 75 |
4.7 特別な型の文脈自由言語と文脈自由文法 76 |
演習問題 78 |
5 プッシュダウン・オートマトン |
5.1 pd-オートマトンとは 81 |
5.2 pd-オートマトンの定義 83 |
5.3 非決定性pd-オートマトンと文脈自由言語 88 |
演習問題 93 |
6 Turing機械 |
6.1 Turing機械 95 |
6.2 Turing機械の定義と表示法 95 |
6.3 Turing機械の構成技法 100 |
6.4 手続としてのTuring機械 107 |
6.5 Turing機械の諸変形 108 |
6.6 基本型に等価な制限されたTuring機械 115 |
演習問題 118 |
7 Turing機械:停止問題,O型言語 |
7.1 概説 120 |
7.2 万能Turing機械 120 |
7.3 停止問題の決定不能性 126 |
7.4 帰納的集合のクラス 128 |
7.5 Turing機械とO型文法 129 |
演習問題 133 |
8 線型有界オートマトンと文脈依存言語 |
8.1 序論 134 |
8.2 線型有界オートマトンと文脈依存言語の関係 135 |
8.3 文脈依存言語は帰納的集合の部分クラスである 136 |
演習問題 138 |
9 言語の演算 |
9.1 序論 139 |
9.2 基本演算のもとでの閉包性 139 |
9.3 写像のもとでの閉包性 143 |
演習問題 154 |
10 時間限定Turing機械およびテープ限定Turing機械 |
10.1 序論 156 |
10.2 諸定義 156 |
10.3 「加速定理」および「テープ節約定理」 159 |
10.4 テープ1本のTuring機械と通過列 167 |
10.5 テープ計算量の下界 172 |
10.6 テープ計算量および時間計算量の階層 176 |
演習問題 182 |
11 文脈自由言語の認識に要する時間とテープ量の限界 |
11.1 序論 185 |
11.2 文脈自由言語の認識に要する時間 185 |
11.3 文脈自由言語の認識に要するテープ量 190 |
演習問題 194 |
12 決定性プッシュダウン・オートマトン |
12.1 序論 196 |
12.2 決定性言語の補集合 197 |
12.3 決定性言語の性質 202 |
12.4 非決定性文脈自由言語 212 |
12.5 LR(k)文法 212 |
演習問題 221 |
13 スタックオートマトン |
13.1 定義 223 |
13.2 スタックオートマトンの変型 227 |
13.3 2方向スタックオートマトンの能力 228 |
13.4 1方向スタックオートマトンの能力 239 |
13.5 スタックオートマトンの帰納性 247 |
13.6 閉包の性質 249 |
演習問題 249 |
14 決定可能性 |
14.1 決定可能な問題とそうでない問題 251 |
14.2 Postの対応問題 252 |
14.3 文脈依存言語に関する問題 260 |
14.4 文脈自由言語の決定不能問題 260 |
14.5 文脈自由言語の曖昧さ 263 |
14.6 決定性文脈自由言語に関する決定不能問題 272 |
14.7 正規,LR(k),文脈自由,文脈依存,O型の各文法に対する決定問題の結果の要約 273 |
演習問題 274 |
文献 277 |
索引 283 |