出版書誌データベース

本書は，情報工学，計算機科学の最も基本的な問題である計算とは何か，言語とは何かに答えるための道具であるオートマトンおよび形式言語理論を学ぶための入門書である。これらの道具は，計算機のハードウェア，ソフトウェアに関連する多くの分野で用いられており，計算機に関わる人にとっては必須の知識といえる。またオートマトンとは，計算機の数学的モデルであり，計算の原理を理解するための数学的な道具である。このように本書は扱う内容から数学的な話題を扱ってはいるが，図と具体例を多くして，理系の読者のみならず，情報系の文系の読者にも取り組めるよう丁寧にわかりやすく書かれている。さらに読者に特別な予備知識を必要としないよう，必要事項はすべて本の中で説明し，容易に理解できるように配慮した。そのため，工業高等専門学校，大学学部の授業テキストとして利用できるだけでなく，情報系の専門学校，企業における研修においても利用することができる。

第1章　準備
1.1　オートマトンと形式言語とは
1.2　オートマトン・言語理論のための準備
1.3　主なオートマトンと形式文法

第2章　有限オートマトン
2.1　決定性有限オートマトン
2.2　状態遷移図

第3章　非決定性有限オートマトン
3.1　非決定性有限オートマトン
3.2　空動作のある非決定性有限オートマトン
3.3　3種類の有限オートマトンの等価性

第4章　最簡形の決定性有限オートマトン
4.1　最簡形の決定性有限オートマトン
4.2　状態の等価性

第5章　正規表現
5.1　正規表現の定義
5.2　正規表現と有限オートマトンの等価性

第6章　正規言語の性質
6.1　正規言語の閉包性
6.2　繰り返し定理
6.3　正規言語でない言語の存在

第7章　形式文法
7.1　形式文法の定義
7.2　文法のクラス

第8章　正規文法と有限オートマトンの等価性
8.1　正規文法と有限オートマトンの等価性
8.2　正規文法の拡張

第9章　文脈自由文法
9.1　文脈自由文法と導出木
9.2　あいまい性
9.3　文脈自由文法の部分クラス

第10章　文脈自由文法の標準形
10.1　文法の簡単化
10.2　Chomsky の標準形
10.3　Greibach の標準形

第11章　プッシュダウンオートマトン
11.1　決定性プッシュダウンオートマトン
11.2　非決定性プッシュダウンオートマトン

第12章　文脈自由文法と非決定性プッシュダウンオートマトンの等価性
12.1　文脈自由文法から非決定性プッシュダウンオートマトンへの変換
12.2　非決定性プッシュダウンオートマトンから文脈自由文法への変換

第13章　文脈自由言語ではない言語
13.1　文脈自由言語の演算に対する閉包性
13.2　文脈自由言語の繰り返し定理
13.3　文脈自由言語ではない言語の存在

第14章　チューリング機械
14.1　チューリング機械とは
14.2　文脈依存文法と線形拘束オートマトンの関係
14.3　句構造文法とチューリング機械の関係

第15章　オートマトンと言語理論の応用
15.1　文字列照合問題への応用
15.2　コンパイラへの応用
15.3　マークアップ言語への応用