計算理論の基礎 [原著第 3 版] 1.オートマトンと言語(ケイサンリロンノキソゲンチョダイサンハンイチオートマトントゲンゴ)

Michael Sipser 教授による “ Theory of Computation ” の講義は MIT 屈指の名講義で、教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた、この分野の標準的教科書である。
定理を述べたあと直ちに証明に取りかからず、証明のアイデアを与える工夫、証明の失敗例に言及して理解を深めさせるなど、随所に講義の雰囲気が感じられる、教育的配慮の行き届いた教科書になっている。
第 3 版では、「決定性文脈自由言語」に関する節が新たに加えられたほか、問題や解答が追加されるとともに、いくつかの話題に関して、第 2 版刊行後の研究の進展について説明を加えた。
第 0 章 序論
0.1 オートマトン,計算可能性,複雑さ
0.2 数学的概念や用語
0.3 定義,定理,証明
0.4 証明のタイプ

第 1 章 正規言語
1.1 有限オートマトン
1.2 非決定性
1.3 正規表現
1.4 非正規言語

第 2 章 文脈自由言語
2.1 文脈自由文法
2.2 プッシュダウン・オートマトン
2.3 非文脈自由言語
2.4 決定性文脈自由言語