オートマトン・形式言語理論
大学，短大，高専等におけるオートマトン・形式言語理論に関する講義のテキスト。多くの例とわかりやすい解説を心がけた。
- 発行年月日
- 2014/04/07
- 判型
- A5
- ページ数
- 190ページ
- ISBN
- 978-4-339-02476-0
- 内容紹介
- 目次
大学，短大，高専等におけるオートマトン・形式言語理論に関する講義のテキストである。本書が扱うのは理論であるが，証明は一切でてこない。多くの例とわかりやすい解説で直観的に考え方を理解できるよう心がけた。
1. 形式言語
1.1 形式言語
1.2 形式言語の識別機械と生成機械
2. 有限オートマトン
2.1 決定性有限オートマトン
2.2 状態遷移図
2.3 非決定性有限オートマトン
2.4 空動作のある非決定性有限オートマトン
2.5 L(dfa) = L(nfa) = L(ε−nfa)
2.6 最簡形の決定性有限オートマトン
2.7 有限オートマトンでは識別できない言語
章末問題
3. プッシュダウンオートマトン
3.1 決定性プッシュダウンオートマトン
3.2 非決定性プッシュダウンオートマトン
3.3 L(dpda) [1] L(npda)
3.4 プッシュダウンオートマトンでは識別できない言語
章末問題
4. チューリング機械と線形拘束オートマトン
4.1 決定性チューリング機械
4.2 非決定性チューリング機械
4.3 線形拘束オートマトン
章末問題
5. 形式文法
5.1 言語の生成システム
5.2 言語の生成システムとしての形式文法
5.3 形式文法の型と形式言語のクラス
5.4 形式文法の標準形
章末問題
6. 有限オートマトンと正規文法
6.1 L(fa) ⊆ L(rg)
6.2 L(fa) ⊇ L(rg)
章末問題
7. プッシュダウンオートマトンと文脈自由文法
7.1 L(npda) ⊆ L(cfg)
7.2 L(npda) ⊇ L(cfg)
章末問題
8. 線形拘束オートマトンと文脈依存文法:
チューリング機械と句構造文法
8.1 L(Tm)=L(psg)
8.2 L(lba)=L(csg)
付録
A.1 集合
A.1.1 集合と要素
A.1.2 集合の表し方
A.1.3 集合の基本演算
A.1.4 集合の包含関係
A.1.5 集合の直積とべき集合
A.2 写像
A.2.1 写像(関数)
A.2.2 写像の分類
A.2.3 逆写像
A.3 グラフ
A.3.1 グラフ
A.3.2 木
引用・参考文献
問の解答
章末問題解答
索引
