Introduction to Automata Theory, Languages, and Computation（オートマトン、言語、計算の理論入門）

引用

Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson.

章の要約

第3版は約535ページに11章を収めており、各章は長い。主題の方法を述べる最初の章は約36ページ、有限オートマトンの第2章は約48ページである。本書は Hopcroft と Ullman の1979年の教科書に由来する。第2版（2000年）から Motwani が加わり、第3版は2006年に出た。Pearson は、この版を、理論的概念を簡潔で分かりやすく示し、実践的な応用を増やすよう更新したものと説明し、当初は Gradiance というオンライン評価ツールが付属していたが、現在は本書に付属しないとしている。章の順序は、この分野の定番の道筋に従う。正則言語、次に文脈自由言語、そしてチューリング機械、決定不能性、難解性である。

第1章：オートマトン：方法と狂気

主題を紹介する約36ページの導入の章で、最初のモデルが定義される前に主題の枠組みを示す。

第2章：有限オートマトン

計算の最初の、最も単純なモデルとしての有限オートマトン。約48ページで、冒頭の章のうちで最長である。Google Books が本書について挙げる頻出語には、非決定性オートマトンと、空列による遷移を持つ非決定性の拡張形である「e-NFA」が含まれる。

第3章：正規表現と正則言語

正規表現と、それが記述する言語。85ページから始まる。

第4章：正則言語の性質

正則言語の性質。題に「性質」を含む2つの章のうちの最初のものである。

第5章：文脈自由文法と文脈自由言語

言語を記述する第二の方法としての文法。導出と構文木は、本書に繰り返し現れる用語に含まれる。

第6章：プッシュダウンオートマトン

文脈自由文法に対応する機械で、決定性プッシュダウンオートマトン（DPDA）も含まれる。DPDA は本文の頻出語に現れる。

第7章：文脈自由言語の性質

文脈自由言語に関する、第4章に対応する章。

第8章：チューリング機械入門

計算の一般的なモデルとしてのチューリング機械で、続く章の出発点になる。

第9章：決定不能性

どのアルゴリズムでも解けない問題。Google Books が挙げる頻出語には、修正ポスト対応問題（MPCP）が含まれる。

第10～11章：難解な問題、さらなる問題のクラス

原理的には解けるが効率的には解けない問題と、それに続く、さらなる問題のクラスを扱う最終の章。Google Books が挙げる頻出語には、多項式時間帰着、3SAT、co-NP、ハミルトン閉路問題が含まれる。

主要概念

第1～4章：正則言語

• 有限オートマトン：計算の最初のモデルで、文法や機械より先に教えられる。
• 正規表現：同じ言語のクラスのための記法。
• 正則言語の性質：閉包と決定に関する問い。

第5～7章：文脈自由言語

• 文脈自由文法と文脈自由言語。
• プッシュダウンオートマトン：スタックを持つ有限オートマトン。
• 文脈自由言語の性質。

第8～11章：計算可能性と計算複雑性

• チューリング機械：計算の一般的なモデル。
• 決定不能性：どのアルゴリズムでも解けない問題。
• 難解な問題とさらなる問題のクラス：効率的な計算の限界。

批判的分析

長所

• 11章で一通りの道筋。 目次は、有限オートマトンから文脈自由言語、チューリング機械を経て、決定不能性と難解性に至るので、1冊で学部の1つの講義全体を扱える。
• 難解性を含む。 第10章と第11章は難解な問題とさらなるクラスを扱うが、Kozen の章の一覧は計算可能性で止まっている。
• 分かりやすさを目指した提示。 Pearson は、簡潔で分かりやすい提示と実践的な応用を強調している。
• 長い実績。 1979年から2006年までの3つの版で、Hopcroft と Ullman が一貫して著者を務め、この分野で影響力のある教科書となっている。

短所

• 旧版より高度な理論が少ない。 本書の歴史に関する記述によれば、第2版以降、応用が拡充され、より高度な理論の一部が取り除かれた。1979年版のより深い内容が必要な講義には、補足の教科書が必要になる。
• 長い章。 冒頭の章が36～48ページあり、短い章を多数並べた教科書に比べるとモジュール性が低い。
• 付属のオンラインツールがない。 第3版に付属していた Gradiance は、Pearson がもはやサポートしていないため、それを軸にした宿題システムは使えない。

コースにおける位置づけ

本書は、形式言語、オートマトン、計算可能性に関する古典的で大きな教科書であり、最も直接の比較対象は Sipser の Introduction to the Theory of Computation である。こちらもオートマトン、形式言語、計算可能性、複雑性への明快な上級入門書である。どちらも主教材になりうる。Kozen の Automata and Computability は、短い章からなるよりコンパクトな代替で、クリーネ代数やゲーデルの定理のような話題まで進むが、計算複雑性の手前で止まる。

Linz と Rodger の An Introduction to Formal Languages and Automata は形式化より説明と具体例を優先し、より多くの説明を求める学生の併読書になる。MacCormick の What Can Be Computed? は同じ理論を Python のプログラムを通して扱い、Arora と Barak の Computational Complexity は第10章・第11章に続く大学院レベルの発展である。

本書の使い方

Pearson のページは予備知識を明示していない。集合、関係、帰納法、証明が妥当な背景であり、プログラミングの経験は実践的な動機づけを理解する助けになる。

実践的な進め方：

• 中核： 正則言語に第1～4章、文脈自由文法とプッシュダウンオートマトンに第5～6章、チューリング機械と決定不能性に第8～9章。
• 初回は軽く： 第4章と第7章の2つの「性質」の章は、初回は軽く読み、証明の技法に慣れてから戻るとよい。
• 任意： 講義が計算複雑性を含むなら第10章と第11章、そうでなければ複雑性の教科書を使う。

演習に取り組み、各モデル（有限オートマトン、文法、プッシュダウンオートマトン、チューリング機械）について、小さな例を手で書き、本が次に教える同等のモデルに変換してみるとよい。