クイックソートはどんなアルゴリズムかと問われれば(割と明確に)答えられるような気がしますが、オートマトンって何？形式言語って何？と質問されても明確に答えられる自信はありません。本書を読み終えた今でも、自信を持って理解できたとは言えないのですが、冒険を通して興味を持つきっかけになっていると思います。
学習意欲が高まったところで、本書の最後で紹介されている参考文献でさらに知識を深めていけたらいいですね。
各章で取り扱っているテーマは以下の通りです。
- 正則言語と有限オートマトン
- 有限オートマトンの決定性・非決定性と正則表現
- 有限オートマトンと実際の機械
- 文脈自由言語とプッシュダウンオートマトン
- 正則言語と文脈自由言語に対する反復補題
- 文脈自由文法とプッシュダウンオートマトンの等価性
- 文脈自由言語の統語解析
- 文脈依存言語と線形拘束オートマトン、チューリングマシン
- 万能チューリングマシン
- 対角線言語と決定不能性
