川添愛の「白と黒のとびら」についての批判を書こうとしているが、いろいろ面倒である。まずプッシュダウンオートマトンと文脈自由文法までの話の展開を比較してみたいと思う。
オートマトン・言語理論の基礎 米田政明監修
以下、この本を米田本として参照する。米田本はこの三冊の中では（情報系の人にとっては）オーソドックスなスタイルである。
- 有限オートマトン
- 非決定性有限オートマトン
- ε動作非決定性有限オートマトン
- 最簡形の決定性有限オートマトン
- （ε動作）決定性プッシュダウンオートマトン
- 非決定性プッシュダウンオートマトン
- 形式文法
- 正規文法と有限オートマトン
- 文脈自由文法とプッシュダウンオートマトン
- オートマトンと形式文法の関係
- 言語の階層構造（繰り返し定理が出て来る）
これで終わりじゃなくてチューリンングマシンの話もあるけど、とりあえず関係ありそうなところだけ並べた。他の本も同様。初めにオートマトンについてまとめて述べて、後から形式文法について述べ、形式文法とオートマトンの関係を述べるという流れである。また、決定性オートマトンについて述べてから、非決定性オートマトンについて述べている。
決定性プッシュダウンオートマトンのε動作については以下の注意書きがある。
すべてのq(∈Q)、Y(∈Γ)について、もしδ(q, ε, Y)が定義されているならば、すべてのa(∈Σ)に対してδ(q, a, Y)は定義されない。--- p64
いやここだけ引用しても記号の定義がないから意味が通じないけれど、ε動作には強い制約があるということである（あるスタックトップ記号に対してε動作があるなら、そのスタックトップ記号と他の入力記号の組み合わせでの遷移はないという意味らしい。これにより決定性が保証される）。
オートマトンは形式文法とは完全に独立に定義されている。学問的に面白い（と私が勝手に思う）ところは、
- 決定性有限オートマトンと非決定性有限オートマトンの受理する言語は同じ
- 決定性プッシュダウンオートマトンと非決定性プッシュダウンオートマトンの受理する言語は違う。（非決定性プッシュダウンオートマトンの方が広く受理する）
- お互い独立に定義された、形式文法の生成する言語と、オートマトンの受理する言語が等しくなる。
オートマトン・言語理論 富田悦次／横森貴共著
- 有限オートマトン
- 非決定性有限オートマトン
- 正規表現
- 形式文法
- 文脈自由文法（反復定理を含む）
- 単純決定性プッシュダウンオートマトン
- 決定性プッシュダウンオートマトン
- 非決定性プッシュダウンオートマトン
- 非決定性プッシュダウンオートマトンと文脈自由文法の相互変換
有限オートマトンの次に形式文法が来て、その後プッシュダウンオートマトンになるという構成である。しかし、米田本にない、単純プッシュダウンオートマトンという項目がある。これはプッシュダウンスタック以外の状態を持たないという形式のオートマトンであり、単純化されている分だけわかりやすい。
そのはずなのだが、状態が一つしかないので、ここでこの文字が来たらそれ以後はどんな文字が来ても受理しないという不受理状態への遷移が出来ない。受理状態というのもないので、入力文字列が終わった時にスタックが空なら受理という定義になる。しかし、入力文字列が終わる前にスタックが空になると困ったことになる。
スタックだけを使ってそういう問題にうまく対応することはできるのだが、この本ではその辺の説明が大幅に不足しているように思う。
決定性プッシュダウンオートマトンのε動作の制限については、米田本と同様に説明があった。それ以上の説明として、ε動作はは事実上その後スタックが空になる時にのみ使われるという説明もあり親切である。
私が個人的に重視する以下の点にはちゃんと触れている。
- 決定性有限オートマトンと非決定性有限オートマトンの受理する言語は同じ
- 決定性プッシュダウンオートマトンと非決定性プッシュダウンオートマトンの受理する言語は違う。（非決定性プッシュダウンオートマトンの方が広く受理する）
- お互い独立に定義された、形式文法の生成する言語と、オートマトンの受理する言語が等しくなる。
白と黒のとびら 川添愛
- 有限オートマトンと簡約化
- 形式言語から有限オートマトンの構成
- 自動販売機としての有限オートマトン（アルファベット三文字）
- ε動作非決定性プッシュダウンオートマトン？
- 反復補題（繰り返し定理）
- 文脈自由文法とプッシュダウンオートマトンの等価性
アルファベット三文字のオートマトンが出てくるのはよい。白と黒は説明が簡単になるように使われているだけで、コンピュータの中では２進数……とかいう話とは一切関係ないことだから。
軽く言及されているだけの部分を除くと、非決定性を扱うのが「４．ε動作非決定性プッシュダウンオートマトン？」なんだよね。いきなり難しいのが出てきたぞ。その結果、私が個人的に重視している
- 決定性有限オートマトンと非決定性有限オートマトンの受理する言語は同じ
- 決定性プッシュダウンオートマトンと非決定性プッシュダウンオートマトンの受理する言語は違う。（非決定性プッシュダウンオートマトンの方が広く受理する）
この二つは登場しない。そして
- 独立に定義された形式文法の生成する言語と、オートマトンの受理する言語が等しくなる。
この部分なのだが、「４．ε動作非決定性プッシュダウンオートマトン？」とクエスチョンマークを付けているように、これは情報系のオートマトンの本で最初に導入されるプッシュダウンオートマトンと比較するとかなり変わっている。実は、米田本の「非決定性プッシュダウンオートマトンと文脈自由文法の相互変換」の部分で、文脈自由文法から構成されるプッシュダウンオートマトンがこの「４．ε動作非決定性プッシュダウンオートマトン？」にそっくりなのだ。つまり、文脈自由文法と独立に定義されたものではなく、文脈自由文法から構成されたものを最初に持ってきているわけだ。これで、後に等価性を示したと言われても、私としては納得できない。
非決定性プッシュダウンオートマトンは難しい
確かに、非決定性というのは難しい。機械というものはいつでも同じ動作をするものという考えがある。その上、決定性有限オートマトンの定義のところで、同じ状態、同じ入力に対していつでも同じ状態遷移をするって定義したわけだし。
それだけでなく、非決定性がある場合、私が重視している「正しくない文法の入力に対しては正しくないと答える」ということが難しくなる。
一方、生成規則にあってオートマトンの非決定性に相当する「同じ非終端記号から二種類以上の生成規則がある」というのは理解しやすいようだ。自然言語でもそういうところがあるから。あるいは、文を作る時には自由に作れるという考えがあるからだろうか。
そこで、非決定性より先に文の生成規則をやって、それに対応させる形で非決定性を導入すればわかりやすいと考えたのかもしれない。いやあ、でも独立性が損なわれてしまうと、その後の等価性の証明が全然証明にならないという重大な問題が発生してしまう。
その上、プッシュダウンオートマトンというものがやたら難しく見えてしまうという問題もある。
まだ、書くかもしれないし、もう書かないかもしれない。
