オートマトン・言語理論入門
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 マークアップ言語への応用