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

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

この分野の有名な入門書。第３版まで出ているが、新版になるにしたがって評判が落ちている。ということで第１版を読むことにした。よくまとまっているし、よく書けているので非常に面白い。informalに内容を説明したあとで、「以上のことを形式化すると」と始まる。この述べ方はとても分かりやすいし、望ましい。

ある言語（文字列の集合）とそれに対応するオートマトンを始めとするアルゴリズムの対応を明らかにするように議論が進む。正則集合と有限オートマトン、文脈自由文法とプッシュダウン・オートマトン、帰納的に枚挙可能な言語とテューリング機械の対応が語られる。だいたい読みやすいのだが、Greibachの標準形のところと、テューリング機械の様々なバリエーションのところはやや困難だった。

この翻訳ではrecursively enumerable setという単語を「帰納的可算集合」と訳している。自分がよく見る訳語は「帰納的に枚挙可能な集合」だ。recursive setは「帰納的集合」と訳される。すると「帰納的可算だが帰納的でない集合」というのは、翻訳だけでは意味不明に見える（帰納的集合とはその所属関係が決定可能である集合）。