計算理論の基礎：オートマトン

どうやら原書は第三版が出てるようだ。

http://www-math.mit.edu/~sipser/book.html

〇読んだ経緯

正規表現技術入門を読んだ際に

参考文献に掲載されていたため読んでみた。

taisyo7333.hatenablog.com

〇読み終わるまでの時間

2週間程度(電車の中で読んだ) 

〇感想 

平易に書かれていると思う。

他の言語理論の書籍の場合は各々の定理に対して

帰納法などを用いた証明が多かったりするが、これはそうではない印象。

(もちろん数学的な証明をして理解することも必要だとは思う。)

証明のアイディアを解説後に証明に入るため理解しやすい。

証明も言葉で説明してある。

しかし、すらすらと読めてしまうため理解したつもりで終わっているかもしれない。

再読すべし。言語理論関連で他の教科書も見てみるかな。てか大学行って計算機科学をキチンと勉強したくなってきた。

【メモ】

・DFAとNFAは等価であり、正規表現も等価であるため変換可能であるということ。

　→　この辺の理解が進めば grep のコード読んで際により深く分かりそうだ。

　　　DFA型の正規表現の場合は、正規表現→NFA→DFA　と変換してDFAをシミュレーションすることで、入力文字列が受理されるか判定する。

・ポンピング補題による非正規言語の証明。

・文脈自由文法とプッシュダウンオートマトン(PDA)の等価性

・ポンピング補題による非文脈自由文法の証明。

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