『オートマトン 言語理論 計算論 Ⅰ』

この記事は本 Advent Calendarの1日目の記事です．（1日目とは？）
adventar.org

本日の本は『オートマトン 言語理論 計算論 Ⅰ』．

オートマトン言語理論 計算論〈1〉 (Information & Computing)

J. Hopcroft, R. Motwani, J. Ullmanの3人による共著の日本語版です．
このうち，HopcroftとUllmanは昨日C&C受賞記念講演をした方です．
C&C受賞記念講演については講演メモを書いたのでそちらもどうぞ:
pandaman64.hatenablog.jp
pandaman64.hatenablog.jp
pandaman64.hatenablog.jp

ⅠとⅡの二巻構成で，Ⅰでは正規表現およびDFA*1，文脈自由文法およびPDA*2を扱います．反復補題もあるよ．
今学期の講義でオートマトンをやっているのでその教科書ですね．
Ⅱは持ってないので良く分からないのですが，決定性問題を扱い文脈自由文法のいくつかの性質が決定不能であることを示すようです．
DFA→PDA→チューリングマシンと扱う対象を広げていってるんですかね．

この本は帰納法の原理から初めて一歩一歩解説を進めていきます．
とはいえ，証明も形式的すぎずすいすい読み進めていくことができます．
例題や章末の演習問題・オートマトンの応用例が豊富なのも嬉しいですね*3．
HopcroftやUllmanが計算機科学の教育でC&C賞を受賞したのも納得という感じの素晴らしい古典です．

今ならオートマトン力も付いているだろうし
www.jstage.jst.go.jp
にも再挑戦してみようかな・・・！

*1:Deterministic Finite Automaton

*2:PushDown Automaton

*3:XMLが出てきたのには時代性を感じますが・・・