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