白と黒のとびら

4130633570川添愛『白と黒のとびら: オートマトンと形式言語をめぐる冒険』(東京大学出版会, 2013)(参考文献リストあり・索引なし)

チョムスキー階層のすべてに対応するオートマトンを「扉を持った遺跡」に例えて組み込んだファンタジー。計算理論の基礎を学ぶのにはふつうの教科書の方がいいだろうが、ひと通り学んだ後なら楽しめるだろう。計算複雑性の理論など、進んだ話題を扱う続編に期待。

線形拘束オートマトン(ゼウ山の塔)への入力が、○と●という2つのボタンなのだが、塔はどうやって入力の終わりを認識しているのだろう。