ジョン・ホップクロフト、ジェフリー・ウルマン『オートマトン 言語理論 計算論 (2)』

オートマトン 言語理論 計算論 (2) (Information & computing (4)) (1986/03) J.ホップクロフト、J.ウルマン 他 商品詳細を見る

下巻では文脈依存文法を導入し、Chomsky階層を解説する。また、決定性文脈自由言語を導入するとともに、決定的言語と非決定的言語で差が出る事例を紹介する。言語の一般的定式を述べた後、いよいよ計算の複雑性の理論へ。もともとP=NPをめぐる話題が読みたくて読書を始めたので、ようやく到達した気分。

その計算の複雑性に関しては初等レベルの記述としてよくできていると感じた。特に、異なる信託oracleを付加してP=NPの成否が変わってしまうという例(p.211-217)は、この問題がいかに解決が難しいかを示していて、とても面白い。次はPapadimitrouあたりを読むか。