Amazon.co.jpで購入する

情報科学書籍一覧　目次

オートマトン言語理論計算論I
Information & Computing　3

ISBN4-7819-0374-6　　サイエンス社

原書： 「Introduction to Automata Theory, Languages, and Computation 」Addison Wesley

John E. Hopcroft / Rajeev Motwani / effrey D. Ullman　著

野崎昭弘（大妻女子大学　教授） 高橋正子（国際基督教大学　教授） 町田　元（一橋大学　教授） 山崎秀記（一橋大学　教授）　訳

A5判　　320ページ　　本体価格\2816　　1984年8月発売

[内容]

オートマトン，言語および計算理論の入門書として高い評価を得ている書の翻訳版．

[目次]

1　準備
1-1　文字列，アルファベット，および言語
1-2　グラフと木
1-3　帰納法による証明
1-4　集合
1-5　関係
1-6　本書の梗概
1-7　演習問題
1-8　演習問題への解答
2　有限オートマトンと正則表現
2-1　有限状態系
2-2　基本的定義
2-3　非決定性有限オートマトン
2-4　ε-動作を含む有限オートマトン
2-5　正則表現
2-6　2方向有限オートマトン
2-7　出力つき有限オートマトン
2-8　有限オートマトンの応用
2-9　演習問題
2-10　演習問題への解答
3　正則集合の性質
3-1　正則集合に対する反復補題
3-2　正則集合の閉包性
3-3　正則集合に対する決定手続き
3-4　Myhill-Nerodeの定理と有限オートマトンの最小化
3-5　演習問題
3-6　演習問題への解答
4　文脈自由文法
4-1　動機と導入
4-2　文脈自由文法
4-3　導出木
4-4　文脈自由文法の簡単化
4-5　Chomskyの標準形
4-6　Greibachの標準形
4-7　本質的に曖昧である文脈自由言語の存在
4-8　演習問題
4-9　演習問題への解答
5　プッシュダウン・オートマトン
5-1　直観的説明
5-2　諸定義
5-3　プッシュダウン・オートマトンと文脈自由言語
5-4　演習問題
5-5　演習問題への解答
6　文脈自由言語の性質
6-1　CFLに対する反復補題
6-2　CFLの閉包性
6-3　CFLに対する決定アルゴリズム
6-4　演習問題
6-5　演習問題への解答
7　テューリング機械
7-1　序
7-2　テューリング機械
7-3　計算可能な言語および関数
7-4　テューリング機械を構成するための技法
7-5　テューリング機械の変更
7-6　Churchの仮説
7-7　テューリング機械による数え上げ
7-8　基本モデルと同等な，制限されたテューリング機械
7-9　演習問題
8　決定不能性
8-1　問題
8-2　帰納的および帰納的可算言語の性質
8-3　万能テューリング機械と決定不能問題
8-4　Riceの定理と決定不能問題
8-5　Postの対応問題の決定不能性
8-6　TMの正しい計算と正しくない計算：CFLに関する問題の決定不能性を示す道具
8-7　Greibachの定理
8-8　帰納的関数論入門
8-9　神託計算
8-10　演習問題
8-11　演習問題への解答

Amazon.co.jpで購入する

情報科学書籍一覧　目次

ISBN4-7819-0432-7　　サイエンス社

原書： 「Introduction to Automata Theory, Languages, and Computation 」Addison Wesley

John E. Hopcroft / Rajeev Motwani / effrey D. Ullman　著

野崎昭弘（大妻女子大学　教授） 高橋正子（国際基督教大学　教授） 町田　元（一橋大学　教授） 山崎秀記（一橋大学　教授）　訳

A5判　　296ページ　　本体価格\2816　　1986年3月発売

[内容]

オートマトン，言語および計算理論の入門書として高い評価を得ている書の翻訳版．

[目次]

1　Chomskyの階層
1-1　正則文法
1-2　一般の文法
1-3　文脈依存言語
1-4　言語のクラス間の関係
1-5　演習問題
1-6　演習問題への解答
2　決定性文脈自由言語
2-1　DPDAの標準形
2-2　DCFLの補集合のもとでの閉包性
2-3　予知機械
2-4　DCFLの他の閉包性
2-5　DCFLの決定問題
2-6　LR(0)文法
2-7　LR(0)文法とDPDA
2-8　LR(k)文法
2-9　演習問題
2-10　演習問題への解答
3　言語族の閉包性
3-1　トリオと強トリオ
3-2　GSM(汎順序機械)写像
3-3　トリオに関するその他の性質
3-4　言語の抽象族
3-5　AFL演算の間の独立性
3-6　まとめ
3-7　演習問題
3-8　演習問題への解答
4　計算の複雑さの理論
4-1　定義
4-2　線型加速，テープ圧縮，テープ数削減
4-3　階層定理
4-4　計算量の測度の間の関係
4-5　移行補題と非決定性の階層
4-6　計算量の測度に関する一般的な性質：間隙定理，加速定理，和定理
4-7　公理論的な計算量の理論
4-8　演習問題
4-9　演習問題への解答
5　手におえない問題
5-1　多項式時間と多項式領域
5-2　いくつかのNP完全問題
5-3　補NP
5-4　PSPACE完全問題
5-5　TとNSPACE(LOG_n)に対する完全問題
5-6　手におえないことが証明可能ないくつかの問題
5-7　神託つきテューリング機械に対するT=NT問題：T=NTの成否を知るために必要なわれわれの能力の限界
5-8　演習問題
5-9　演習問題への解答
6　他の重要な言語
6-1　補助テープつきプッシュダウン・オートマトン
6-2　スタック・オートマトン
6-3　インデックス言語
6-4　成長システム
6-5　まとめ
6-6　演習問題
6-7　演習問題への解答