計算理論の基礎 原著第2版(1) オートマトンと言語

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

• 販売会社／発売会社: 共立出版
• 発売年月日: 2008/05/25
• JAN: 9784320122079

商品レビュー

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ページあまり．オートマトンと言語理論の基礎が学べる好著．

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