白と黒のとびら解説 - 毎朝30分読書会

これがそれぞれ以下の形式言語のクラス/文法に対応する

ううむ、こういう言語の分類があるのですね。

各章のテーマについて

古代ルル語系は正則言語
第3章は非決定性オートマトンと決定性オートマトンとその変換について
第4章は自動販売機の設計に潜むオートマトンがテーマだったらしい。どうりでちょっと浮いてると思った!
古代クフ語は文脈自由言語
- 筒がスタック
- ε-遷移あり
正則言語と文脈自由言語に対する反復補題
文脈自由言語の統語解析
第一古代セティ語は文脈依存言語。塔は線形拘束オートマトン
万能チューリングマシン
- 「塔」の動作を指定するのに偽クフ語を利用した点については補足されていました。やっぱりね
- 状態、テープ記号、ヘッドの移動方向に整数を割りあてる

これで「白と黒のとびら」の読書は終了です。ストーリーもゃんと読めて、おもしろい本でした。

次からは「型システム入門」に進みます。大作ですね。何ヶ月かかることか…。