I　計算理論とは

1講　系列を操作するしくみ
　　問題

2講　計算理論のあらまし
　　2.1　計算理論の誕生
　　2.2　問題，手順，計算モデル
　　2.3　チューリング機械のロバスト性
　　2.4　この本のあらまし
　　2.5　この本の構成

3講　再帰
　　3.1　再帰的定義と組み立てルール
　　3.2　ハノイの塔問題を解く手順の再帰的定義
　　問題

4講　数学的準備
　　4.1　集合
　　4.2　系列と言語
　　4.3　関数と問題
　　4.4　グラフ
　　4.5　論理演算とド・モルガンの法則
　　4.6　定理と証明
　　4.7　アルゴリズムの記述
　　問題

II　有限オートマトンと正規表現

5講　有限オートマトンの動き
　　問題

6講　有限オートマトンの設計
　　問題

7講　有限オートマトンの定義
　　7.1　有限オートマトンの形式的定義
　　7.2　受理の定義
　　問題

8講　非決定性有限オートマトンの定義
　　8.1　非決定性有限オートマトンの形式的定義
　　8.2　受理の定義
　　問題

9講　決定性有限オートマトンと非決定性有限オートマトンの等価性
　　9.1　非決定性有限オートマトンを模倣する決定性有限オートマトンの例
　　9.2　非決定性有限オートマトンから等価な決定性有限オートマトンへの変換
　　問題

10講　正規表現
　　10.1　正規表現rが表す言語L(r)とそれを受理する状態遷移図M(r)
　　10.2　正規表現rと言語L(r)の関係
　　問題

11講　正規表現と有限オートマトンの等価性
　　11.1　階層的状態遷移図への等価変換のあらまし
　　11.2　状態遷移図から等価な正規表現への変換アルゴリズム
　　11.3　計算モデル間の模倣
　　問題

12講　有限オートマトンの受理能力の限界
　　問題

13講　正規言語のクラスの閉包性
　　問題

III　プッシュダウンオートマトンと文脈自由言語

14講　文脈自由文法の定義
　　問題

15講　正規文法，文脈自由文法，文脈依存文法
　　15.1　正規文法による系列の生成と有限オートマトンによる系列の受理
　　15.2　文脈自由文法とあいまい性
　　15.3　文脈依存文法の定義
　　15.4　チョムスキーの階層
　　問題

16講　文脈自由文法の設計
　　問題

17講　チョムスキーの標準形
　　問題

18講　文脈自由文法の言語生成能力の限界
　　問題

19講　プッシュダウンオートマトンの定義
　　問題

20講　プッシュダウンオートマトンによる文脈自由文法のシミュレーション
　　問題

21講　文脈自由文法によるプッシュダウンオートマトンのシミュレーション
　　問題

IV　計算可能性

22講　チューリング機械の定義
　　22.1　チューリング機械の形式的定義
　　22.2　チューリング機械の受理の定義
　　22.3　チャーチ・チューリングの提唱
　　問題

23講　多テープチューリング機械
　　問題

24講　決定性チューリング機械と非決定性チューリング機械の等価性
　　問題

25講　万能チューリング機械
　　問題

26講　チューリング機械の停止問題
　　26.1　停止問題の決定不能性
　　26.2　言語の認識と言語の決定
　　問題

27講　ポストの対応問題の決定不能性
　　27.1　ポストの対応問題の決定不能性
　　27.2　帰着
　　問題

解答
文献
謝辞
索引