書記の読書記録#47「計算理論の基礎　1 オートマトンと言語」

M.Sipser「計算理論の基礎　1 オートマトンと言語」のレビューと読書記録

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

原著（第3版）：

Introduction to the Theory of Computation

レビュー

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

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

重要な概念リスト

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

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

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

・正規演算の閉包性

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

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

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

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

読書記録

＃ 1p1〜73
・計算機の本質的な能力と限界・複雑さ，計算可能性，オートマトン・数学的概念：集合，関数，グラフ，文字列と言語，ブール論理・定義，定理，証明・決定性有限オートマトン（DFA）：状態Q，アルファベットΣ，遷移関数δ（Q×E→Q），開始状態q0，受理状態の集合F，正規演算：和集合演算，連結演算，スター演算・非決定性有限オートマトン（NFA）：遷移関数δ（Q×Σε→P(Q)）・NFAとDFAの等価性，正規演算が閉じている

＃ 2p73〜158
・正規表現の定義・字句解析・有限オートマトンとの等価性・一般非決定性有限オートマトン（GNFA）・非正規言語とポンピング補題，鳩の巣原理・文脈自由文法：変数V，終端記号Σ，規則の有限集合R，開始変数S・構文解析との対応・曖昧さ・Chomsky標準形・プッシュダウンオートマトン（PDA）：スタックをもつ・PDAと文脈自由言語の等価性・非文脈自由言語：ポンピング補題

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

書記の読書記録まとめ｜Writer_Rinka｜note