オートマトン言語理論計算論 1 (Information&Computing 3)
- サイエンス社 (1984年8月1日発売)
本棚登録 : 22人
感想 : 1件
本ページはアフィリエイトプログラムによる収益を得ています
- Amazon.co.jp ・本 (303ページ)
- / ISBN・EAN: 9784781903743
感想・レビュー・書評
-
この分野の有名な入門書。第3版まで出ているが、新版になるにしたがって評判が落ちている。ということで第1版を読むことにした。よくまとまっているし、よく書けているので非常に面白い。informalに内容を説明したあとで、「以上のことを形式化すると」と始まる。この述べ方はとても分かりやすいし、望ましい。
ある言語(文字列の集合)とそれに対応するオートマトンを始めとするアルゴリズムの対応を明らかにするように議論が進む。正則集合と有限オートマトン、文脈自由文法とプッシュダウン・オートマトン、帰納的に枚挙可能な言語とテューリング機械の対応が語られる。だいたい読みやすいのだが、Greibachの標準形のところと、テューリング機械の様々なバリエーションのところはやや困難だった。
この翻訳ではrecursively enumerable setという単語を「帰納的可算集合」と訳している。自分がよく見る訳語は「帰納的に枚挙可能な集合」だ。recursive setは「帰納的集合」と訳される。すると「帰納的可算だが帰納的でない集合」というのは、翻訳だけでは意味不明に見える(帰納的集合とはその所属関係が決定可能である集合)。詳細をみるコメント0件をすべて表示
全1件中 1 - 1件を表示