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

計算機に原理的に何が解けて、何が解けないのか。それを数学として扱う計算理論の分野で、長く読み継がれてきた教科書が Michael Sipser 氏の『Introduction to the Theory of Computation』です。『計算理論の基礎 [原著第 3 版] 1.オートマトンと言語』はその原著第 3 版の日本語版第 1 巻で、田中圭介氏 / 藤岡淳氏 / 阿部正幸氏 / 植田広樹氏 / 太田和夫氏の翻訳により共立出版から 2023 年 4 月に刊行されました。版元の紹介文は本書を「この分野の標準的教科書」と位置づけ、MIT 屈指の名講義と評される Sipser 氏の講義のノートをもとにまとめられた経緯を伝えています。

日本語版は全 3 巻、原著第 3 版の分冊構成

日本語版は分冊構成をとり、本巻「オートマトンと言語」に続いて、第 2 巻「計算可能性の理論」と第 3 巻「複雑さの理論」が 2023 年 5 月に刊行されています。原著の章立てを 3 冊に分けた形なので、チューリング機械や決定不能性、P 対 NP といった計算理論の後半戦は続巻の守備範囲です。原著第 3 版での更新点として、版元の紹介文は「決定性文脈自由言語」に関する節の新設、問題と解答の追加、第 2 版刊行後の研究の進展に関する説明の追加を挙げています。原著第 2 版の邦訳も同じ共立出版から出ており、本書はその改訳 / 改版にあたります。すでに旧版で学んだ人が買い直すかどうかは、この追加分に価値を感じるかで判断するとよいでしょう。

第 0 章の証明入門から文脈自由言語まで、本巻の範囲

本巻の目次は第 0 章から始まります。序論にあたる第 0 章はオートマトン / 計算可能性 / 複雑さという分野全体の見取り図に加えて、数学的概念や用語、定義 / 定理 / 証明、証明のタイプの整理に紙幅を割いており、集合や論理に不安がある読者の足場になります。第 1 章は正規言語で、有限オートマトン、非決定性、正規表現、非正規言語を扱い、第 2 章は文脈自由言語で、文脈自由文法、プッシュダウン・オートマトン、非文脈自由言語、決定性文脈自由言語へ進みます。制限の強い計算モデルから始めるのは、単純なモデルほど「何ができて何ができないか」を完全に特徴づけられ、証明の練習台として最適だからです。この理論は実務と地続きでもあります。テキスト処理で使う正規表現エンジンの背後にあるのは有限オートマトンの理論であり、コンパイラやパーサの構文解析は文脈自由文法の応用そのものです。

「証明のアイデア」を先に示す講義由来の書き方

この本の書き方の特徴として、版元の紹介文は、定理を述べたあと直ちに証明に取りかからず先に「証明のアイデア」を与える工夫と、証明の失敗例に言及して理解を深めさせる構成を挙げています。計算理論の学習で本当に難しいのは個々の定理の暗記ではなく、証明を読み、自分で組み立てる力そのものです。直観的なアイデアを先に示してから形式化する二段構えは、読者が証明を自分の手で再構成する訓練として機能します。第 0 章に証明のタイプの整理が置かれているのも同じ配慮の一部で、数学書を読み慣れていない読者への導入として働きます。

本巻で元が取れるのは、情報系学部で計算理論やオートマトンの講義を受けている学生、そして正規表現やパーサを日常的に使いながら「この処理はそもそも正規表現で書けるのか」を理論の根拠を持って判断できるようになりたいエンジニアです。読み終えると、言語のクラスという物差しで問題の難しさを測る視点が手に入ります。一方、すぐに使えるデータ構造やアルゴリズム実装の技法を求める人には向きません。その目的ならアルゴリズム本の選び方で扱っている系統の本が近道で、本書は「なぜ解けるのか・解けないのか」を支える理論側の 1 冊です。数学的な証明を読む根気は要りますが、その入口は第 0 章が丁寧に用意してくれています。腰を据えて理論を積み上げたい人にとって、まず手に取るべき第 1 巻です。