計算理論の基礎 原著第2版(1) の商品レビュー

MichaelSipser【著】,太田和夫,田中圭介【監訳】,阿部正幸,植田広樹,藤岡淳,渡辺治【訳】

2022/11/11

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

2020/12/10

原著はM.Sipser“Theory of Computation”で，邦訳ではテキストが3分割されている。よって1巻自体のページは短い。

それでも内容は十分に濃く，以下の概念について具体例交えて解説されている。

重要な概念リスト

・有限オートマトンの定義，設計

・正規演算：和集合演算，連結演算，スター演算

・決定性有限オートマトン（DFA）と非決定性有限オートマトン（NFA）の定義，等価性

・正規演算の閉包性

・正規表現の定義，一般化非決定性有限オートマトン（GNFA）との等価性

・ポンピング補題と非正規言語，非文脈自由言語

・文脈自由文法の定義，設計，Chomsky標準形

・プッシュダウンオートマトン（PDA）の定義，文脈自由文法との等価性

2018/01/26

「白と黒のとびら」を読んで，少しオートマトンの勉強でもしてみるかと，手に取る．一言，非常にいい本．フォーマルな定義を述べる前に，定義のアイディアのわかるような例が述べられ理解を助ける．定理は明確に述べられ，証明の前にそのアイディアがうまく説明されて，証明に入っても迷子にならないように工夫されている．証明が終わると，証明を適用する具体例がいくつか．これも理解を助ける．文献，さくいんが長いので，演習問題をまぜても150ページあまり．オートマトンと言語理論の基礎が学べる好著．

読みながら学生時代に，有限オートマトンをはじめチューリングマシンなどを授業でならったのを思い出した．そして，意外に簡単に思い出せる．若い時に勉強するっって大事ね．

2017/11/03

計算理論の教科書です。オートマトンについての説明が主です。前半はかなりわかりやすかったです。文字列検索などで日頃お世話になっている正規表現が非決定性有限オートマトンで出来ていると書かれているページを読んだときはちょっと衝撃でした。正規表現ってどんな仕組みなんだろうと疑問に思っていたので一気にそれが解消されてとてもスッキリしました。良かったです。