An Introduction to Formal Languages and Automata（形式言語とオートマトン入門）

引用

Linz, P., & Rodger, S. H. (2023). An Introduction to Formal Languages and Automata (7th ed.). Jones & Bartlett Learning.

章の要約

第7版は2部17章からなる。第I部「Theory」は第6版の14章に新しい演習を加えたもので、第II部「Applications」は新設され、その理論をコンパイラの構文解析に応用する。続いて付録が2つ、一部の演習の解答とヒント、参考文献があり、全体で約570ページになる。アスタリスクの付いた節は、後の内容に支障なく省略できる。各章の末尾には、従来の演習に加えて、やさしい「Introductory Exercises（導入演習）」が新たに置かれている。

第1章：Introduction to the Theory of Computation（計算理論入門）

数学的な準備（集合、関数と関係、グラフと木、証明の技法）を復習し、本書の三つの基本概念である言語、文法、オートマトンを導入する。省略可能な節で応用を概観する。

第2章：Finite Automata（有限オートマトン）

決定性有限受理機を遷移グラフとともに定義し、それを使って正規言語を定義する。続いて非決定性受理機を導入し、非決定性がなぜ役立つのかを説明して、両者の等価性を証明する。省略可能な節で状態数の削減を扱う。

第3章：Regular Languages and Regular Grammars（正規言語と正規文法）

正規表現を導入し、それがちょうど正規言語を記述することを証明する。単純なパターンの記述への利用も扱う。右線形文法と左線形文法が同じ言語族を生成することを示す。

第4章：Properties of Regular Languages（正規言語の性質）

集合演算やその他の演算に関する閉包性、基本的な判定問題、そして鳩の巣原理とポンピング補題を使って言語が正規でないことを示す方法を扱う。

第5章：Context-Free Languages（文脈自由言語）

文脈自由文法、最左導出と最右導出、導出木を導入し、構文解析、所属問題、曖昧性へと進み、最後にプログラミング言語における文脈自由文法の役割を述べる。

第6章：Simplification of Context-Free Grammars and Normal Forms（文脈自由文法の簡単化と標準形）

無用な生成規則、λ生成規則、単位生成規則の除去方法を示し、チョムスキー標準形とグライバッハ標準形を提示する。省略可能な節で文脈自由文法の所属判定アルゴリズムを与える。

第7章：Pushdown Automata（プッシュダウンオートマトン）

非決定性プッシュダウンオートマトンを定義し、文脈自由文法との等価性を両方向から証明する。続いて決定性プッシュダウンオートマトンと決定性文脈自由言語を扱い、その文法について省略可能な節を置く。

第8章：Properties of Context-Free Languages（文脈自由言語の性質）

文脈自由言語と線形言語のポンピング補題、閉包性、文脈自由言語のいくつかの決定可能な性質を示す。

第9章：Turing Machines（チューリング機械）

標準的なチューリング機械を言語の受理機として、また変換器として定義し、複雑な作業のために機械を組み合わせる方法を示して、チューリングの提唱を述べる。

第10章：Other Models of Turing Machines（チューリング機械の他のモデル）

変種（停留オプション付き、片側無限テープ、オフライン機械）、より複雑な記憶をもつ機械（多テープ、多次元）、非決定性機械、万能チューリング機械、線形有界オートマトンを検討し、どの変種が能力を増やさないかを確かめる。

第11章：A Hierarchy of Formal Languages and Automata（形式言語とオートマトンの階層）

帰納的言語と帰納的可算言語を区別し、それぞれのクラスに属さない言語を示す。続いて制限なし文法と文脈依存文法を導入し、チョムスキー階層を組み立てる。

第12章：Limits of Algorithmic Computation（アルゴリズム的計算の限界）

計算可能性と決定可能性、停止問題、ある決定不能問題から別の問題への帰着、帰納的可算言語と文脈自由言語に関する決定不能問題、ポストの対応問題を扱い、最後に効率の問題を短く取り上げる。

第13章：Other Models of Computation（計算の他のモデル）

別の計算モデルを示す。原始帰納的関数とμ帰納的関数（アッカーマン関数を含む）、ポストシステム、そして行列文法、マルコフアルゴリズム、Lシステムなどの書き換え系である。

第14章：An Overview of Computational Complexity（計算複雑性の概観）

チューリング機械のモデルと複雑性を関係づけ、言語族と複雑性クラスを導入する。PとNP、NP問題の例、多項式時間帰着、NP完全性を扱い、PがNPに等しいかという未解決問題で終わる。

第15–17章：Compilers and Parsing（コンパイラと構文解析）；LL Parsing（LL構文解析）；LR Parsing（LR構文解析）

第II部は、コンパイラの働き、下向き構文解析と上向き構文解析、FIRST関数とFOLLOW関数から始まる。第16章は、LL構文解析のために文脈自由文法を非決定性プッシュダウンオートマトンに変換し、LL(1)構文解析表と構文解析アルゴリズムを構成し、LL(k)の節を置く。第17章は同じことをLR構文解析について行う。項目と閉包、構文解析スタックをモデル化するDFA、LR(1)構文解析表とアルゴリズム、λ生成規則、構文解析の衝突である。

付録

付録Aは有限状態変換器（ミーリ機械とムーア機械、その等価性、最小化、限界）を扱う。付録Bは、オートマトンや文法を作って試すための無料の対話型ツールJFLAPを紹介する。

主要概念

第1–4章：基礎と正規言語

• 言語、文法、オートマトン：本書の三つの基本概念で、第1章でまとめて導入される。
• 非決定性：複数の動作の可能性を許すこと。有限受理機では便利さは増すが、能力は増えない。
• 正規表現：有限オートマトンが受理する言語をちょうど記述する表記法。
• ポンピング補題：すべての正規言語がもつ性質で、ある言語が正規でないことの証明に使われる。

第5–8章：文脈自由言語

• 導出木と曖昧性：導出の構造と、一つの文字列に複数の木を許す文法。
• チョムスキー標準形とグライバッハ標準形：どの文脈自由言語にも与えることのできる、制限された文法の形。
• プッシュダウンオートマトン：スタックをもつ有限オートマトンで、非決定性のものは文脈自由文法と等価である。

第9–13章：チューリング機械と計算可能性

• チューリングの提唱：機械的な計算はすべてチューリング機械で実行できるという主張。
• 万能チューリング機械：他の任意の機械をその記述から模倣する機械。
• チョムスキー階層：正規、文脈自由、文脈依存、帰納的可算という入れ子になった言語族。
• 停止問題と帰着：基本的な決定不能問題と、他の問題が決定不能であることを示すための方法。

第14章：複雑性

• PとNP：決定性および非決定性の多項式時間で解ける問題。
• NP完全性：多項式時間帰着のもとでNPの中で最も難しい問題。

第15–17章：構文解析

• FIRSTとFOLLOW：構文解析表を作るために使う、文法記号上の関数。
• LL(1)構文解析とLR(1)構文解析：1記号の先読みを使う、表駆動の下向き・上向き構文解析で、プッシュダウンオートマトンから導かれる。

批判的分析

長所

• 直観と例が先。 序文によれば、本書は直観的な動機づけと例による説明を重視し、簡潔でも難解な議論よりわかりやすい議論を選び、中心的な概念を動機づけとなる例から導入する。
• 問題を解きながら学ぶ。 各節末の演習は、本文の続きを一歩進めるだけのやさしいものから非常に難しいものまである。第7版は、難しい演習への橋渡しとして章末の導入演習を加えた。一部の演習には解答とヒントが付く。
• 「何の役に立つのか」への直接の答え。 第II部はプッシュダウンオートマトンと文法をLL構文解析とLR構文解析に応用する。著者によれば、理論の実用性を問う学生の声に応えたものである。
• ツールの支援。 付録Bは無料の対話型ツールJFLAPを紹介している。序文は、概念の理解と演習の解答作成の時間短縮のために、これを強く勧めている。

短所

• 簡潔な証明。 序文は、多くの証明が動機だけを示し、決まりきった細部を省いていることを認めている。完全な形式的証明を求める読者は、より厳密な教科書を参照するか、自分で手順を補う必要がある。
• 複雑性は概観のみ。 計算複雑性は1章だけで、NP完全性で終わる。空間計算量やその先の話題は扱われない。
• 1学期には収まりきらない。 序文によれば、第I部の大部分を1学期で扱うには重点の取捨選択が必要であり、第II部を入れるには第I部の後半の節を軽く扱う必要がある。

コースにおける位置づけ

計算理論のコースの中で、本書は有限オートマトンからNP完全性までの標準的な流れをたどる、取りつきやすい最初の教科書である。もう一つの入門的な選択肢である MacCormick の What Can Be Computed? は、Pythonのプログラムを通じて計算可能性と複雑性に取り組むもので、有限オートマトンには1章しか割かず、文法やプッシュダウンオートマトンの章はない。授業が形式言語に多くの時間を割くなら Linz と Rodger のほうが合っており、両者は互いによく補い合う。

Kozen の Automata and Computability（完全な証明付きの短い講義の集まり）、Hopcroft、Motwani、Ullman の Introduction to Automata Theory, Languages, and Computation、Sipser の Introduction to the Theory of Computation は、似た範囲をより形式的な証明とともに扱う。Linz の証明の概略が短すぎると感じる学生は、それらの対応する節を読むとよい。Arora と Barak の Computational Complexity は、第14章の概観をはるかに超えて複雑性を扱う大学院向けの教科書である。

本書の使い方

序文が想定する読者は、コンピュータサイエンスとコンピュータ工学の2年生と3年生である。前提として、高水準プログラミング言語の知識、データ構造とアルゴリズムの基礎、そして集合、関数、関係、論理、数学的推論を含む離散数学の授業（不可欠とされる）を挙げている。

• 中核（第I部）： 第1–12章を順に読む。序文は、アスタリスク付きの節（たとえば1.3、2.4、6.3、7.4）を除けば、後で困らずに飛ばせるところはほとんどないと注意している。
• 軽く扱う部分： 序文によれば、第I部の後半の多くの節は、流れを損なわずに軽く扱うか省略でき、それで第II部のために1週間ほどを確保できる。計算の他のモデルを扱う第13章はその候補になる。
• 複雑性： 第14章はP、NP、NP完全性の最初の見取り図を与える。
• 応用（第II部）： 第15–17章は、コンパイラの授業に進む学生や、授業時間が足りない場合の指導付きの読書に向いている。

まず導入演習で各定義の理解を確かめ、それから本来の演習へ進むとよい。例に出てくるオートマトンと文法はすべてJFLAPで作り、証明を書く前に文字列で試してみること。本書が証明の概略だけを示すところでは、欠けている細部を自分で書き出すこと。序文が勧めているのはこの練習である。