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

著者 : Michael Sipser 太田和夫 田中圭介 阿部正幸 植田広樹 藤岡淳 渡辺治

• 共立出版 (2008年5月21日発売)

作品紹介・あらすじ

　M.Sipser教授の“Theory of Computation”の講義はMIT屈指の名講義で，教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた，この分野の標準的教科書である。
　定理を述べたあと直ちに証明に取りかからず，証明のアイデアを与える工夫，証明の失敗例に言及して理解を深めさせるなど，随所に講義の雰囲気が感じられる，教育的配慮の行き届いた教科書になっている。
　今回第2版では，初版の内容に「選ばれた問題」に対する解答を追加するとともに，いくつかの話題に関して，初版後の研究の進展について説明を加えた。

感想・レビュー・書評

[debuipipiさんの感想 · 2018年1月26日]

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

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

[獅子丸さんの感想 · 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）の定義，文脈自由文法との等価性

[Koji Higasaさんの感想 · 2019年4月30日]

証明が丁寧でとてもいい

[0xC0FFEEさんの感想 · 2017年11月3日]

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

[nextschoolさんの感想 · 2009年7月11日]

[借本]

[UmiNanaさんの感想 · 2008年11月15日]

基礎本。