電子情報通信レクチャーシリーズ B-6
オートマトン・言語と計算理論
計算機では，解ける問題，解けない問題，解けることは解けるが時間がかかって手に負えない問題の3種類が存在する。このことを把握するため，計算機のモデルを正確に理解し上手に使えるように指導するのが本書の目的である。
- ジャンル
- 発行年月日
- 2003/11/06
- 判型
- B5
- ページ数
- 186ページ
- ISBN
- 978-4-339-01821-9
- 内容紹介
- 目次
計算機では，解ける問題，解けない問題，解けることは解けるが時間がかかって手に負えない問題の3種類が存在する。このことを把握するため，計算機のモデルを正確に理解し上手に使えるように指導するのが本書の目的である。
１．言語とは何か・なぜ必要か
1.1 文章の意味を理解する
1.2 文章の正しさを解析する
1.3 形式言語を導入する
本章のまとめと文献
理解度の確認
２．正規表現と有限オートマトン
2.1 正規表現
2.2 有限オートマトン
2.3 非決定性有限オートマトン
2.4 有限オートマトンと正規表現の等価性
2.5 有限オートマトンの能力の限界
本章のまとめと文献
理解度の確認
３．文脈自由文法
3.1 文脈自由文法の重要性
3.2 文脈自由文法
3.3 文脈自由文法と正規言語
3.4 文脈自由文法の標準形
3.5 文脈自由文法で生成できない言語
本章のまとめと文献
理解度の確認
４．プッシュダウンオートマトン
4.1 プッシュダウンオートマトン
4.2 プッシュダウンオートマトンの設計
本章のまとめと文献
理解度の確認
５．チューリング機械と０型文法
5.1 チューリング機械
5.2 ０型文法
5.3 チューリング機械によっても認識できない言語
本章のまとめと文献
理解度の確認
６．チューリング機械の停止性と決定問題
6.1 チューリング機械の停止性
6.2 非可解な問題
6.3 ポストの対応問題
本章のまとめと文献
理解度の確認
７．NP完全問題
7.1 クラスPとクラスNP
7.2 NP完全性
本章のまとめと文献
理解度の確認
８．最近の話題―あとがきにかえて―
8.1 固定パラメータ容易性
8.2 対数領域限定計算
本章のまとめと文献
索引
