オートマトン 言語理論計算論I

書影

Information & Computing  3

オートマトン 言語理論計算論I

定価:
3,098
(本体:2,816円+税)

発行日:1984年8月1日

発行:サイエンス社

ISBN:978-4-7819-0374-3

サイズ:並製A5

ページ数:320ページ

在庫:品切れ

内容詳細

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

目次

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 万能テューリング機械と決定不能問題\r
8-4 Riceの定理と決定不能問題\r
8-5 Postの対応問題の決定不能性
8-6 TMの正しい計算と正しくない計算:CFLに関する問題の決定不能性を示す道具
8-7 Greibachの定理
8-8 帰納的関数論入門
8-9 神託計算
8-10 演習問題
8-11 演習問題への解答

サポート情報

関連書籍

Fortran77プログラミング

原田賢一

1,815円(税込)

入門
CによるカオスCG

川上 博上田哲史

2,860円(税込)

中級
情報処理[第3版]

草薙信照

2,200円(税込)

入門