あらすじ

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　決定性文脈自由言語

書籍情報