見出し画像

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

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


レビュー

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

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


読書記録

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

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


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


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


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



学習に必要な本を買います。一覧→ https://www.amazon.co.jp/hz/wishlist/ls/1XI8RCAQIKR94?ref_=wl_share