情報
オートマトン・言語理論の基礎
本書は大学や短大あるいは高専における授業のテキストとして書かれている｡
オートマトン･言語理論が扱う題材は多岐にわたるが、本書では思い切って根本的な問いと課題に題材を絞り、その分丁寧にわかりやすく説明することとした｡これらの問いと課題に答えていく中で、計算機科学あるいは情報工学の基礎としてのオートマトン理論並びに形式言語理論の持つ考え方が理解でき、その美しさと面白さを十分に味わうことができるからである｡
本書が扱うのは理論であるが、本文中に証明は一切ない｡わかりやすさのために厳密さを犠牲にした訳ではない｡考え方を理解するのに必要なのは多数の例とわかりやすい説明とをもとに学生･生徒諸君が自分で考えることであり、証明は不要だからである｡
大学や短大･高専で学ぶ1人でも多くの人がオートマトン･言語理論の基礎を理解し、モデルを用いて推論することの美しさと面白さを体得することによって、ますます進展する高度情報化社会で伸びていくための素養を身につけていただきたい｡本書が少しでもその役に立てば幸いである｡
紙の書籍¥2,500定価（税別）
基本情報
| 発売日 | 2003年5月10日 |
|---|---|
| ページ数 | 264 ページ ※印刷物 |
| サイズ | A5 |
| ISBN | 9784764902978 |
| ジャンル | 情報 |
| タグ | 情報科学, 教科書 |
| 電子書籍形式 | 販売なし |
主要目次
第1章序論
1.1 オートマトン･言語理論の内容
1.1.1 オートマトンとは
1.1.2 語とは何か,言語とは何か
1.1.3 形式文法とは
1.1.4 本書で学ぶ内容
1.2 オートマトン･言語理論を学ぶための準備
1.2.1 集合の表し方
1.2.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(npda)⊃≠L(dpda)
3.4 プッシュダウンオートマトンでは受理できない言語
【演習問題】
第4章 チューリング機械
4.1 言語の識別機械としてのチューリング機械
4.2 非決定性チューリング機械
4.3 線形拘束オートマトン
[話題4.1] 計算機械としてのチューリング機械
[話題4.2] 2スタックオートマトン
[話題4.3] 人間と有限オートマトン,人間とチューリング機械
【演習問題】
第5章 形式文法と形式言語
5.1 言語の生成装置としての形式文法
5.2 形式文法のクラスと形式言語のクラス
5.3 正規文法と正規言語
5.4 文脈自由文法と文脈自由言語
5.5 文脈依存文法と文脈依存言語
5.6 句構造文法と句構造言語
【演習問題】
第6章 オートマトンと形式文法の関係
6.1 正規文法と有限オートマトン
[話題6.1] 正規表現
6.2 文脈自由文法とプッシュダウンオートマトン
6.3 文脈依存文法と線形拘束オートマトン
6.4 句構造文法とチューリング機械
6.5 まとめと話題
[話題6.2] 文法の標準形
【演習問題】
第7章 言語の階層構造
7.1 正規言語の性質と正規言語ではない言語の存在
7.2 文脈自由言語の性質と文脈自由言語ではない言語の存在
[話題7.1] あいまいな言語について
7.3 文脈依存言語の性質と文脈依存言語ではない言語の存在
7.4 句構造言語の性質と句構造言語ではない言語の存在
【演習問題】
解答
参考文献
1.1 オートマトン･言語理論の内容
1.1.1 オートマトンとは
1.1.2 語とは何か,言語とは何か
1.1.3 形式文法とは
1.1.4 本書で学ぶ内容
1.2 オートマトン･言語理論を学ぶための準備
1.2.1 集合の表し方
1.2.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(npda)⊃≠L(dpda)
3.4 プッシュダウンオートマトンでは受理できない言語
【演習問題】
第4章 チューリング機械
4.1 言語の識別機械としてのチューリング機械
4.2 非決定性チューリング機械
4.3 線形拘束オートマトン
[話題4.1] 計算機械としてのチューリング機械
[話題4.2] 2スタックオートマトン
[話題4.3] 人間と有限オートマトン,人間とチューリング機械
【演習問題】
第5章 形式文法と形式言語
5.1 言語の生成装置としての形式文法
5.2 形式文法のクラスと形式言語のクラス
5.3 正規文法と正規言語
5.4 文脈自由文法と文脈自由言語
5.5 文脈依存文法と文脈依存言語
5.6 句構造文法と句構造言語
【演習問題】
第6章 オートマトンと形式文法の関係
6.1 正規文法と有限オートマトン
[話題6.1] 正規表現
6.2 文脈自由文法とプッシュダウンオートマトン
6.3 文脈依存文法と線形拘束オートマトン
6.4 句構造文法とチューリング機械
6.5 まとめと話題
[話題6.2] 文法の標準形
【演習問題】
第7章 言語の階層構造
7.1 正規言語の性質と正規言語ではない言語の存在
7.2 文脈自由言語の性質と文脈自由言語ではない言語の存在
[話題7.1] あいまいな言語について
7.3 文脈依存言語の性質と文脈依存言語ではない言語の存在
7.4 句構造言語の性質と句構造言語ではない言語の存在
【演習問題】
解答
参考文献