kenju's blog

About Programming and Mathematics

『Understanding Computation』を読んだ

実際に読んだのはだいぶ前のことだけど、思い出したように記事に起こしておく。

決定性有限オートマトン・非決定性有限オートマトンの話から始まり、決定性/非決定性プッシュダウンオートマトンチューリングマシン、ラムダ計算やコンビネータの話へと展開されていく。

本書が非常に読みやすかったのは、Ruby でサンプルコードを紹介しながら進めていく点だ。理論とコードを適切に行き来しながら説明することで、説明がすっと頭の中に入ってきた。

有限オートマトンを用いて正規表現を実装してみたり、プッシュダウンオートマトンを用いた字句解析・構文解析の例も紹介することで、それら計算機モデルが現実世界でどのような課題を解決するのかへの理解も深めることができた。

今後新しいプログラミング言語を勉強するときの、練習材料としても本書のサンプルコードを元に移植してみるネタとしても良い。

良い本でした。

サンプルコード

https://github.com/kenju/understanding_computation