原著は米国ポートランド大学を中心に幅広く教科書として採用され、3rd Editionを重ねるまでになっています。
本書は全3分冊でコンピュータ数学の基礎分野を網羅する新しい独習シリーズの第3冊目となり、プログラミング分野でも汎用性の高い「コンパイラ」の動作原理でもある「計算論（計算可能性）」に関して、解説しています。「正規言語とオートマトン」「文脈自由語」「チューリングマシン」そして「計算の概念（計算可能性）」、P/NP問題など、数学を学ぶ方はもちろんコンピュータの動作原理の研究やソフトウェア開発に携わる方にも関係の深いトピックの解説と演習がコンパクトにまとまった好著です。
『Binary Hacks』 『Write Great Code』 『The Artof Computer Programming』 など名著と呼ばれるコンピュータ書やチューリング、チョムスキー、ゲーデル、ラッセル＆ホワイトヘッド等の読者層に特にお薦めの一冊です。
11.1 正規言語
11.1.1 正規表現
11.1.2 正規表現の代数
11.2 有限オートマトン
11.2.1 決定性有限オートマトン
11.2.2 非決定性有限オートマトン
11.2.3 正規表現を有限オートマトンへ変換する
11.2.4 有限オートマトンを正規表現へ変換する
11.2.5 出力装置としての有限オートマトン
11.2.6 有限オートマトンを表現して実行する
11.3 効率的な有限オートマトンを構成する
11.3.1 正規表現からNFAへのもう１つのアルゴリズム
11.3.2 NFAをDFAへ変換する
11.3.3 最少状態のDFA
11.4 正規言語のトピックス
11.4.1 正規文法
11.4.2 正規言語の性質
11.5 章のまとめ
12.1 文脈自由言語
12.2 プッシュダウンオートマトン
12.2.1 受理の同値形
12.2.2 文脈自由文法とプッシュダウンオートマトン
12.2.3 プッシュダウンオートマトンを表現し実行する
12.3 文脈自由構文解析
12.3.1 LL(k)文法による下向き構文解析
12.3.2 上向き構文解析とLR(k)文法
12.4 文脈自由言語のトピックス
12.4.1 文法を変換する
12.4.2 文脈自由言語の性質
12.5 章のまとめ
13.1 チューリングマシン
13.1.1 チューリングマシンの定義
13.1.2 出力のあるチューリングマシン
13.1.3 異なる定義
13.1.4 万能チューリングマシン
13.2 チャーチ ＝ チューリングの提唱
13.2.1 計算モデルの同値性
13.2.2 単純なプログラミング言語
13.2.3 帰納的関数
13.2.4 文字列を変換するマシン
13.3 章のまとめ
14.1 計算可能性
14.1.1 有効列挙
14.1.2 停止問題
14.1.3 全体問題
14.1.4 その他の問題
14.2 言語の階層
14.2.1 言語
14.2.2 まとめ
14.3 計算量のクラス
14.3.1 クラスP
14.3.2 クラスNP
14.3.3 クラスPSPACE
14.3.4 扱いにくい問題
14.3.5 完全性
14.3.6 形式的計算量理論
14.4 章のまとめ
ギリシャ文字
記号
参考文献
索引
【法人・教育機関のお客様へ】新年度の大口注文・お見積りなど、お気軽にご相談ください
デザインやコーディングなど、Webデザインに役立つスキルが身につく書籍を揃えました
テキスト生成、画像生成、動画生成など、生成AI活用のスキルが身につく本をご紹介
新社会人の役に立つスキルが身につく本。ビジネスパーソンとしてスタートダッシュを切ろう！
小学校から必修化！人気の『ルビィのぼうけん』ほかプログラミング教育の本はこちら
開発・ビジネス・マーケティング・EC運営・営業支援など、幅広いジャンルの講座を開催
