書記の読書記録#32「白と黒のとびら：オートマトンと形式言語をめぐる冒険」

川添愛「白と黒のとびら：オートマトンと形式言語をめぐる冒険」のレビューと読書記録

白と黒のとびら

レビュー

『偉大な魔法使いに弟子入りした平凡な少年の物語』，本書はロード・ダンセイニの作品より着想を得たのだという。背景にはオートマトンの理論。◯と●のみからなる言語を元に，その規則性を探っていく。

物語を読む感覚で，オートマトンの考え方をなんとなく掴んでいくような本。物語としてゆっくり読み進めていくのがいいと思う。

読書記録

物語のネタバレかどうか分からないが，（読解に役立つことを期待して）背景知識のみここに列挙しておく。

＃ 1p1〜121
・正則言語と有限オートマトン・有限オートマトンの決定性，非決定性・正則表現・有限オートマトンの例・文脈自由言語・プッシュダウンオートマトン，スタック，ε動作

＃ 2p122〜240
・正則言語と文脈自由言語に対する反復補題・文脈自由言語とプッシュダウンオートマトンの等価性・統語解析（構文解析）

＃ 3p241〜316
・文脈依存言語のクラス，線形拘束オートマトン，チューリングマシン・万能チューリングマシン・対角線言語：チューリングマシンを記述しない文字列，自身が記述するチューリングマシンによって受理されない文字列

本記事のもくじはこちら：

書記の読書記録まとめ｜Writer_Rinka｜note