書記の読書記録#32「白と黒のとびら：オートマトンと形式言語をめぐる冒険」
川添愛「白と黒のとびら：オートマトンと形式言語をめぐる冒険」のレビューと読書記録
レビュー
『偉大な魔法使いに弟子入りした平凡な少年の物語』，本書はロード・ダンセイニの作品より着想を得たのだという。背景にはオートマトンの理論。◯と●のみからなる言語を元に，その規則性を探っていく。
物語を読む感覚で，オートマトンの考え方をなんとなく掴んでいくような本。物語としてゆっくり読み進めていくのがいいと思う。
読書記録
物語のネタバレかどうか分からないが，（読解に役立つことを期待して）背景知識のみここに列挙しておく。
＃ 1p1〜121
・正則言語と有限オートマトン・有限オートマトンの決定性，非決定性・正則表現・有限オートマトンの例・文脈自由言語・プッシュダウンオートマトン，スタック，ε動作
＃ 2p122〜240
・正則言語と文脈自由言語に対する反復補題・文脈自由言語とプッシュダウンオートマトンの等価性・統語解析（構文解析）
＃ 3p241〜316
・文脈依存言語のクラス，線形拘束オートマトン，チューリングマシン・万能チューリングマシン・対角線言語：チューリングマシンを記述しない文字列，自身が記述するチューリングマシンによって受理されない文字列
本記事のもくじはこちら：
