書籍批判：オートマトン・言語理論第二版 富田悦次／横森貴 共著

まず、川添愛による「白と黒のとびら」の批判をしようと思ったのだが、そのためにオートマトンの本としてこの本を調べた結果、先にこの本の批判をしようと思った次第である。

だが、それが面倒くさい。すでに書く前から気力喪失している。こんなん書いても誰も読まないし、せいぜい反応するのは著者の援護する人くらいだろうし、誰のためにもならんじゃないの。だるい。

しかし、俺も手斧を持ったはてな民。逆襲が予想されようとも手斧を振るうのだ。

形式言語とオートマトンと生成文法

形式言語というのがあって、これは言語の意味は問わずに、文法だけを問題にする。ある言語の文法に一致するかどうかだけを問題にするのである。その場合に文法を判定する方法が二つある。

ひとつは、文法に合っている文も合っていない文もどちらも受け付けて、その上で、この文は文法に合っている、この文は文法に合っていないという判定を下すという方法である。この判定を行う機械がオートマトンである。

もうひとつは文の生成規則を定めて、その生成規則から生成される文はすべて文法に合っているし、生成される文でなければ文法に合っていないとする方法である。文法に合った文は一般には無限に存在するので、文を全部生成してみせることは出来ない。

自然言語でも似たようなことはあって、日本人が聞いて日本語だと思うものが日本語であるという判定と、日本人が話す言葉が日本語であるという判定に対応すると考えてもよいだろう。

オートマトンとプログラム

一方、オートマトンというのは自動人形というその語源からしても、機械やコンピュータプログラムのモデル化であるとも考えられる。自動販売機のモデルとも言える。オートマトンに対しては同じ動作を行うコンピュータプログラムが作成できる。（あー、非決定性を考えるとちょっと嘘だな）

オートマトン・言語理論 第二版

オートマトン・言語理論 [第2版]

で、そういうオートマトンと形式言語の理論というのは情報科学では、基礎的な理論ということで、学生向けのやさしい教科書が何種類も出版されている。ワシが独学で情報系の勉強をした時には、「岩波講座情報科学６：オートマトン・形式言語理論と計算論」という本を読んだものだが、なかなか難しくて理解できなかったものじゃ。しかし今は情報科の学生向けの本でもやさしい本がたくさんあってうらやましい。

やさしい、わかりやすい本

しかしながら、コンピュータについて多少なりとも知っている人なら、気が付くかもしれないが、やさしい、わかりやすいことを目的とした本がわかりやすいとは限らない。

そもそも「わかる」とはどういうことかという定義をしなければ正確な議論は出来ないのだが、その定義自体が紛糾するので、議論が始まらないという問題がある。しかし、「プログラマーがあるオートマトンの概念をわかる」という点については「そのオートマトンを表すプログラムを作れる」というように定義してもよいのではないか。わかったつもりになっていても実際にはわかっていないことは多いのである。わかってるならプログラムを作れってことだ。それがプログラマーである。オートマトンの理論には難しいオブジェクト指向も関数型プログラミングも圏論も知る必要はない。

プッシュダウンオートマトン

さて、私が上記の本で問題にしているのはプッシュダウンオートマトンの記述である。だいたいオートマトンの本では、有限オートマトンはやさしく、プッシュダウンオートマトンから難しくなり、チューリングマシンは難しいっていう感じなのだが、そのへんはやさしい本でも変わることはない。やさしい本の記述の主体はプッシュダウンオートマトンになる。というかプッシュダウンオートマトンと文脈自由文法の関係が本のクライマックスと言えるだろう。

そしてプッシュダウンオートマトンの主役であるスタックはプログラマーならよく知っているデータ構造である。そしてプログラマーでない人でも知っておいて損のない、比較的簡単で重要な概念である。説明はwikipedea:スタックでも見て欲しい。

実は「白と黒のとびら」でもそんな風なところが気になって確認のために、上記の「オートマトン・言語理論第二版」を読んだ次第なのである。

オートマトン・言語理論第二版　例４．９

上の画像は、「オートマトン・言語理論第二版」の120ページの例4.9からの引用である。このプッシュダウンオートマトンをプログラマーの人は理解してプログラムを作ることが出来るだろうか？　記号の意味などを調べるためには是非上のリンクから本を購入して読んで欲しい。その上で、この例のオートマトンのプログラムを作れれば、わかった理解したということになるだろうし、作れなければわかりにくい、理解しにくいということになるだろう。

さらに理解を助けるためにスタックがどう変化するかという図もある。

上の画像は、「オートマトン・言語理論第二版」の121ページの図4.9からの引用である。図まであって分かりやすいから簡単にプログラムが作れるであろう。

では、プログラムのテストのためのテストケースを挙げておこう。

• 入力 → 出力
• ab → 正しい（文法どおり）
• aabb → 正しい（文法どおり）
• baabb → 正しくない（文法違反）
• abb → 正しくない（文法違反）
• aaba → 正しくない（文法違反）

このテストケースを満たすプログラムが作れたかな？　俺には作れなかったよ。 どうしてこうなった？

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

わからない時には、更に別の本を参照するのである。それが文献探索の底なし沼というもの。

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

 この本にも当然ながらプッシュダウンオートマトンについての記述がある。そして、上の例題をプログラムする上で決定的に重要な情報が書かれていた。

　動作を停止したときの状態qnが受理状態の１つ（Ｆの要素）で、pd-スタックが空である（αnが空で、ボトムマーカーZ0のみである）なら、Mは入力ωを受理する。反対に、状態qnが受理状態の１つでない、あるいは、pd-スタックが空でないなら、Mは入力ωを拒否する。すべての入力を読み終わる前に、動作関数が定義されていなくて動作を停止することもあるが、その場合にも入力ωを拒否すると考える。

 「オートマトン・言語理論の基礎」67ページより。数学記号がうまく表現できていないが、記号の意味などは、上記リンクからこの本を購入して確認して欲しい。

この情報があればプログラムを作ることができるが、分かりやすくはない。俺ならこういう記述があったら、動作が定義されていないところでは例外を投げる。しかし例外を投げっぱなしでは先のテストケースに落ちるので、例外をキャッチしてテストケースに合うような値を返すようにするだろう。

しかし、それでは正しいとは言えないだろう。それはプッシュダウンオートマトンの定義に合っているかどうか分からないのである。プッシュダウンオートマトンは極めて限定的な機械なので好き勝手にプログラムしてはいけないのだ。

私なりの解決

例4.9でちゃんと動作を定義するのが、正しい、そしてわかりやすい解決であろう。

数学記号を表示できないので簡略な書き方にする。スタックトップがSで、入力がbの時スタックトップのSをXにするという場合に（S, b) → X と書くことにすると追加する規則はこうなる。

• （S, b）→ X
• （B, a）→ X
• （X, a）→ X
• （X, b）→ X

 しかし、なんということでしょう。これではまだテストケースを通らないのだ。実に難しい、わかりにくい例である。abbという入力をどうするか？ これは米田氏の本ならスタックボトムに記号があるので解決可能なのだが、富田・横森両氏の本ではうまくいかないのである。（スタックが空の場合はスタックトップを参照できないのである）*1

そもそも富田・横森両氏の本では、状態遷移規則にない入力が来た場合の動作についての何も書かれていないので、もともとどうにもならないのである。（こんなことを書いていて、実は本のどこかに書いてあったら私の大恥である。そして、私の人生にはそれに匹敵するような大恥は何度もあるのだ）

結論

プログラムが作れないということは、本の説明がわかりにくいということだ。……と思うのだが、どうだろうか。

結論その２：ユニットテスト、テストケースという考え方は強い。

但し書き

このブログに書かれていることは、著者の個人的見解であり、著者の所属する組織の公式見解ではない。

*1:スタックが空かどうかプログラムで判定することは出来るので、毎回スタックが空であるかどうか判定を入れるということは可能である。ただし、状態遷移規則はスタックトップを参照する形でしか書けないのが問題である。