MITのOCWに講義動画がある。https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/ 本書も、動画も、教育的配慮が行き届いており、分かりやすい。 オートマトンという数学的マシーンを作っていくのだが、パズルのような面白さがある。

原著はM.Sipser“Theory of Computation”で，邦訳ではテキストが3分割されている。よって1巻自体のページは短い。 それでも内容は十分に濃く，以下の概念について具体例交えて解説されている。 重要な概念リスト ・有限オートマトンの定義，設計 ・正規演算：和集合演算，連結演算，スター演算 ・決定性有限オートマトン（DFA）と非決定性有限オートマトン（NFA）の定義，等価性 ・正規演算の閉包性 ・正規表現の定義，一般化非決定性有限オートマトン（GNFA）との等価性 ・ポンピング補題と非正規言語，非文脈自由言語 ・文脈自由文法の定義，設計，Chomsky標準形 ・プッシュダウンオートマトン（PDA）の定義，文脈自由文法との等価性

「白と黒のとびら」を読んで，少しオートマトンの勉強でもしてみるかと，手に取る．一言，非常にいい本．フォーマルな定義を述べる前に，定義のアイディアのわかるような例が述べられ理解を助ける．定理は明確に述べられ，証明の前にそのアイディアがうまく説明されて，証明に入っても迷子にならないように工夫されている．証明が終わると，証明を適用する具体例がいくつか．これも理解を助ける．文献，さくいんが長いので，演習問題をまぜても150ページあまり．オートマトンと言語理論の基礎が学べる好著． 読みながら学生時代に，有限オートマトンをはじめチューリングマシンなどを授業でならったのを思い出した．そして，意外に簡単に思い出せる．若い時に勉強するっって大事ね．