独習コンピュータ科学基礎III 計算構造 コンピュータプログラムの原理を学ぶ

第11章　正規言語と有限オートマトン

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へのもう1つのアルゴリズム
　　　11.3.2　NFAをDFAへ変換する
　　　11.3.3　最少状態のDFA
11.4　正規言語のトピックス
　　　11.4.1　正規文法
　　　11.4.2　正規言語の性質
11.5　章のまとめ

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

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章　チューリングマシンおよびそれと同値な計算モデル

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章　計算の概念

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　章のまとめ

付録

ギリシャ文字
記号
参考文献

索引

付属データはこちら

お問い合わせ

内容についてのお問い合わせは、正誤表、追加情報をご確認後に、お送りいただくようお願いいたします。

正誤表、追加情報に掲載されていない書籍内容へのお問い合わせや
その他書籍に関するお問い合わせは、書籍のお問い合わせフォームからお送りください。

利用許諾に関するお問い合わせ

本書の書影（表紙画像）をご利用になりたい場合は書影許諾申請フォームから申請をお願いいたします。
書影（表紙画像）以外のご利用については、こちらからお問い合わせください。