オートマトン・言語理論の基礎

本書は大学や短大あるいは高専における授業のテキストとして書かれている。
オートマトン・言語理論が扱う題材は多岐にわたるが、本書では思い切って根本的な問いと課題に題材を絞り、その分丁寧にわかりやすく説明することとした。これらの問いと課題に答えていく中で、計算機科学あるいは情報工学の基礎としてのオートマトン理論並びに形式言語理論の持つ考え方が理解でき、その美しさと面白さを十分に味わうことができるからである。

本書が扱うのは理論であるが、本文中に証明は一切ない。わかりやすさのために厳密さを犠牲にした訳ではない。考え方を理解するのに必要なのは多数の例とわかりやすい説明とをもとに学生・生徒諸君が自分で考えることであり、証明は不要だからである。
大学や短大・高専で学ぶ 1 人でも多くの人がオートマトン・言語理論の基礎を理解し、モデルを用いて推論することの美しさと面白さを体得することによって、ますます進展する高度情報化社会で伸びていくための素養を身につけていただきたい。本書が少しでもその役に立てば幸いである。

『オートマトン・言語理論の基礎』 (米田 政明 著 / 監修、広瀬 貞樹、大里 延康、大川 知 著、近代科学社、2003 年 5 月刊) は、大学や短大、高専の授業のテキストとして書かれたオートマトン理論と形式言語理論の教科書です。版元の紹介文によれば、題材を根本的な問いと課題に絞って丁寧に説明する方針で、扱うのは理論でありながら本文中に証明は一切ありません。厳密さを犠牲にしたのではなく、考え方を理解するには多数の例とわかりやすい説明をもとに自分で考えることが必要で、証明は不要だという立場です。証明の読み書きに慣れる前の段階で、オートマトンと言語の考え方そのものをつかみたい学生に向いた一冊です。

有限オートマトンから言語の階層構造まで、全 7 章の流れ

第 1 章「序論」は、オートマトン、語と言語、形式文法とは何かを整理し、集合と写像の表し方を準備として確認します。続く 3 章は機械の側から順に積み上げる構成で、第 2 章が有限オートマトン (状態遷移図、非決定性、空動作、最簡形、有限オートマトンで識別できない言語)、第 3 章がプッシュダウンオートマトン、第 4 章がチューリング機械と線形拘束オートマトンです。第 4 章には、計算機械としてのチューリング機械や 2 スタックオートマトン、人間と有限オートマトン、人間とチューリング機械を題にした話題の囲みも置かれています。第 5 章で視点を言語の生成装置としての形式文法へ移し、正規文法、文脈自由文法、文脈依存文法、句構造文法の 4 つのクラスを取り上げたあと、第 6 章でそれぞれの文法とオートマトンの対応を示し、第 7 章「言語の階層構造」で各クラスの性質と、そのクラスに属さない言語の存在を扱います。すべての章の末尾に演習問題があり、巻末に解答と参考文献が付きます。版元のページでは講義資料の提供も案内されています。

文法と機械の対応が実務の道具を理解する土台になる

この分野の要は、言語を生成する文法と、言語を受理する機械が 4 段の階層で対応しているという見取り図です。正規文法は有限オートマトン、文脈自由文法はプッシュダウンオートマトン、文脈依存文法は線形拘束オートマトン、句構造文法はチューリング機械に対応し、正規から句構造へ進むほど表せる言語のクラスが広がります。この対応は実務の道具にそのまま現れています。プログラムの字句解析や 正規表現 による検索の背後には有限オートマトンがあり、有限個の状態しか持たない機械は入れ子の深さを数えられないため、任意の深さの括弧の対応を正規表現だけで判定することはできません。括弧や入れ子の構造を扱うには文脈自由文法とスタックが必要で、これが コンパイラー の構文解析の基礎になります。画面遷移や通信プロトコルの設計で使う ステートマシン も、有限オートマトンの考え方を設計に持ち込んだものです。どの道具でどこまで表せるのかという限界の感覚は、この理論を一度通っておくと身につきます。

証明なしの方針が合う人と、合わない人

数学の準備としては、第 1 章で集合と写像の表し方を確認してから本題に入る構成です。一方で、証明を使わないという方針は目的によっては物足りなさにつながります。定理を自分で証明する力を養いたい人や、大学院入試や研究に向けて厳密な議論の型を身につけたい人は、証明を軸に展開する教科書と組み合わせる必要があります。また、目次には決定不能性や計算量を主題にした節はないため、計算可能性や計算の複雑さまで一冊で学びたい場合は別の本が必要です。2003 年刊の本ですが、扱う内容は理論の基礎であり、刊行年による古さが問題になりにくい分野です。

オートマトンや形式言語の授業で、定義の記号に追われて考え方が見えなくなっている学生や、正規表現や構文解析を日常的に使いながらその限界の理由を一度筋道立てて理解したい技術者にとって、例と説明で機械と文法の対応を順にたどれる本書は、証明中心の教科書に進む前の足場を固める一冊になります。