計算理論の基礎　[原著第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　決定性文脈自由言語