白と黒のとびら

この本に書かれているのは、偉大な魔法使いに弟子入りした平凡な少年の物語です。彼は魔法使いになるための勉強をしていく中で、奇妙な「遺跡」と奇妙な「言語」に出会い、それらに隠された秘密に迫っていきます。物語はもちろんフィクションですが、お話を読み終える頃には読者の皆様はいつのまにか、現実の学術上の理論ー情報科学・数学・認知科学における、ある重要な理論ーの基本的な概念に慣れ親しんでいらっしゃることと思います。

『白と黒のとびら』は、オートマトンと形式言語という情報科学の基礎理論を、魔法使いに弟子入りした少年の冒険物語に乗せて伝える本です。著者は川添 愛、版元は東京大学出版会で、2013 年 4 月に刊行されました。副題は「オートマトンと形式言語をめぐる冒険」です。版元ドットコムの紹介文によれば、主人公の少年ガレットは魔法使いになるための勉強を進めるなかで、奇妙な「遺跡」や「言語」に出会います。読者は主人公と一緒にパズルを解きながら読み進める仕立てです。数式の定義から入る教科書とは入口が違うため、計算理論の講義を前に全体の見通しを持ちたい人や、教科書で一度つまずいた人の再入門に向きます。

プロローグから第 16 章、解説までの物語の構成

目次は「プロローグ」に始まり、第 1 章「遺跡」、第 2 章「帰郷」、第 3 章「復元」と続いて、第 16 章「返答」と「エピローグ」で物語が閉じ、巻末に「解説」が置かれています。章題は第 4 章「金と銀と銅」、第 7 章「呪文」、第 9 章「不毛な論争」、第 13 章「塔」のように物語の出来事を表す言葉で、定理や理論の用語は章題に出てきません。楽天ブックスの書誌の紹介文も、物語はフィクションでありながら、読み終える頃には情報科学 / 数学 / 認知科学における重要な理論の基本的な概念に慣れ親しめると説明しています。版元ドットコムの紹介文では、プロローグと第 1 章を PDF で試し読みできることと、著者による正誤表が公開されていることも案内されています。

有限オートマトンと形式言語が情報科学の土台になる理由

オートマトンは、入力の記号を 1 つずつ読みながら、有限個の状態の間を規則に従って移っていく抽象的な機械です。読み終えた時点の状態で入力を受理するかどうかが決まるため、記号列の集まり、つまり言語を定義する道具として働きます。形式言語の理論は、言語を生み出す規則である文法と、それを判定する機械の強さを対応づけて整理します。有限オートマトンで判定できる正規言語は 正規表現 で書けるパターンと対応し、括弧の対応のような入れ子の構造を扱うには、スタックを持つプッシュダウンオートマトンと文脈自由文法が必要になります。この階層は、コンパイラー の字句解析と構文解析、通信プロトコルの検証、UI やワークフローを ステートマシン として組む実装など、実務の多くの場面の土台です。一方で教科書は集合と記号の定義から始まり、証明を追わないと先へ進めないため、抽象の段階でつまずく学習者が少なくありません。

計算理論の教科書の前に読む人、教科書と組み合わせる人

本書は主人公と一緒にパズルを解きながら読む形式なので、オートマトンと形式言語の概念に、記号の定義より先に手を動かす側から触れられます。推薦の言葉を寄せた新井紀子氏は、「すべての誤解は『辞書さえあれば言葉の意味なんてわかる』という思い込みから始まる」と書き、言葉の意味をめぐる思い込みを問い直す本として紹介しています。反対に、定理の証明や演習問題で試験や講義に備えたい人には、これ 1 冊では足りません。目次に演習の章は無く、形式的な定義と証明を身につける段では別に教科書が要ります。

情報系の学生で講義の前に理論の見通しを持っておきたい人、正規表現や構文解析を日常的に使いながら背景の理論を知らずにきたエンジニア、言葉と計算の関係に興味がある読者にとって、物語として最後まで読み通せる本書は、計算理論への最初の 1 冊として手に取りやすい選択です。教科書に進む前に、まずガレットの冒険から始めてみてください。