オートマトン・言語理論の基礎(オートマトンゲンゴリロンノキソ)

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

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

コンパイラはなぜ構文エラーを検出できるのか、正規表現はなぜ任意のネスト構造をマッチできないのか。こうした問いの背景にある数学的な枠組みを扱うのが、オートマトンと形式言語の理論です。本書は情報科学を学ぶ学部生向けの教科書として書かれており、有限オートマトン、正規言語、文脈自由文法、プッシュダウンオートマトン、チューリング機械という古典的なトピックを、定義と証明を丁寧に追いながら積み上げていきます。

数学的な厳密さを保ちつつも、証明のステップを省略せずに展開する構成のため、集合と写像の基本さえ押さえていれば独学でも読み進めることができます。大学の講義で副読本として使われるケースも多く、証明の流れを自分の手でなぞる訓練に適しています。

応用的なコンパイラ設計や自然言語処理に直結する本ではありませんが、これらの分野に進む前に「計算可能性とは何か」「言語のクラスにはどんな階層があるか」という土台を固めておくと、応用書で出会う形式的な議論の見通しが格段によくなります。計算機科学の古典に触れたいが、英語の教科書にいきなり挑むのはハードルが高いという方にとって、日本語で読める堅実な選択肢です。