はじめて学ぶオートマトンと言語理論
森北出版
著者：藤原暁宏
まえがき
第1章 オートマトンとは
1.1 計算ってなんだろう
1.2 オートマトンという概念
1.3 オートマトンのための数学的準備
1.3.1 集合の概念と記述方法
1.3.2 要素と集合の関係,および,集合と集合の関係
1.3.3 集合演算
1.3.4 関数
1.4 オートマトンの数学的定義(順序機械)
演習問題
第2章 有限オートマトン
2.1 言語ってなんだろう
2.1.1 言語の種類と概念
2.1.2 言語のための数学的準備
2.1.3 言語の定義
2.2 変換機械と認識機械
2.3 有限オートマトンとは
2.3.1 有限オートマトンの概要
2.3.2 有限オートマトンの定義
2.3.3 状態遷移図と状態遷移表
2.3.4 有限オートマトンの例
2.4 有限オ―トマトンの作り方
演習問題
第3章 さまざまな有限オートマトンと有限オートマトンの限界
3.1 非決定性有限オートマトン
3.1.1 非決定性有限オートマトンとは
3.1.2 非決定性有限オートマトンの定義
3.1.3 非決定性有限オートマトンの例
3.1.4 決定性有限オートマトンヘの変換
3.2 空動作をもつ有限オートマトン
3.2.1 空動作をもつ有限オートマトンとは
3.2.2 空動作をもたない非決定性有限オートマトンヘの変換
3.3 拡張された有限オートマトンと決定性有限オートマトンの関係
3.4 オートマトンの等価性
3.5 有限オートマトンの簡単化
3.6 有限オートマトンの限界
演習問題
第4章 正規表現(有限オートマトンの応用)
4.1 正規表現とは
4.2 正規表現のための数学的準備
4.3 正規表現の定義
4.4 正規表現と有限オートマトンの関係
4.4.1 正規表現から有限オートマトンヘの変換
4.4.2 有限オートマトンから正規表現への変換
演習問題
第5章 プッシュダウンオートマトン
5.1 プッシュダウンオートマトン
5.1.1 プッシュダウンスタックとは
5.1.2 プッシュダウンオートマトンの概要
5.1.3 プッシュダウンオートマトンの状態遷移
5.1.4 プッシュダウンオートマトンの定義
5.1.5 プッシュダウンオートマトンの例と状態遷移図
5.2 非決定性プッシュダウンオートマトン
5.3 プッシュダウンオートマトンの限界
演習問題
第6章 チューリング機械
6.1 チューリング機械とは
6.1.1 チューリング機械の概要
6.1.2 チューリング機械の状態遷移
6.1.3 チューリング機械の定義
6.1.4 チューリング機械の例
6.2 チューリング機械と現在のコンピュータ
6.3 万能チューリング機械
演習問題
第7章 形式文法入門と正規文法
7.1 文法ってなんだろう
7.2 形式文法の定義
7.3 形式文法と言語
7.4 有限オートマトンと形式文法の類似性
7.5 正規文法とは
7.5.1 正規文法の定義
7.5.2 正規文法の例
7.6 正規文法と有限オートマトンの関係
7.6.1 正規文法から有限オートマトンヘの変換
7.6.2 有限オートマトンから正規文法への変換
演習問題
第8章 文脈自由文法
8.1 文脈自由文法とは
8.1.1 文脈自由文法の定義
8.1.2 文脈自由文法の例
8.2 文脈自由文法の簡単化
8.2.1 空記号列生成規則の除去
8.2.2 単位生成規則の除去
8.2.3 無効記号を含む生成規則の除去
8.2.4 簡単化された文脈自由文法
8.3 文脈自由文法の標準形
8.3.1 チョムスキー標準形
8.3.2 グライバッハ標準形
8.4 実用的な文脈自由文法とBNF
演習問題
第9章 オートマトンと形式文法の関係
9.1 プッシュダウンオートマトンと文脈自由文法の関係
9.1.1 文脈自由文法から非決定性プッシュダウンオートマトンヘの変換
9.1.2 プッシュダウンオートマトンから文脈自由文法への変換
9.2 チューリング機械と同じ能力をもつ文法
9.2.1 句構造文法
9.2.2 句構造文法とチューリング機械の関係
9.3 チョムスキーの言語階層
9.4 言語階層の外側
演習問題
参考文献
演習問題解答
索引