[Tokyo.pm] mastering regex

[NAKAMURA, Hiroshi]

なひです．

> From: maeda ＠ src.ricoh.co.jp
> Sent: Tuesday, December 14, 1999 6:40 PM

> なひさん> 正規表現マッチングエンジンにおけるNFAとDFAは，駆動エンジンを，
> なひさん> 正規表現とターゲットのどちらにするかという違いだというのが，
> なひさん> あの本を読んでのなひ理解です（怪しい ^^;）．
> 
> ん～、やはりひとつもDFAの状態遷移図がないところがJeffreyの本の弱
> 点でしょうか。

そういえばありませんでしたね．意図的に外してあるんでしょうか．
追える人には，さっくりオートマトン流の説明をしたほうが早いかもですね．

# なひは．．．^^;

> なひさん> 自機駆動で迷路を解くとなると，
> なひさん> 「迷路ゲーム」は，どうやってもNFAに思えてしまう．．．
> 
> DFAは空間歪曲装置によって、迷路自体を行き止まりのない(そのかわり、
> ゴールが複数ある)ものに変形してしまう、ってのではどうでしょうか。
> 分岐はあるんだけど、後戻りは必要ないっていうところで(マッチしな
> い場合はいつの間にかループを通って出発点に戻ってきている)。

後戻りが必要ない（最初に全て迷路を解析してしまっているので，
迷路ではなくただの一本道に見える），というのは
いいかもしれませんね．空間歪曲装置によって一本道になっているので，
自機は全速力で駆け抜けるだけ．間で敵機を複数匹撃破して回って，
最後に一番でかい（親玉の）首だけ持ってゴール．

NFAだと自機が「こっちの方向に親玉が居る」というヒューリスティクスを
持って突き進んでいき，敵機を見つけたらそいつの首を持ってゴール．
もしかするとそいつは親玉でない可能性もあるけどまぁいいや．

うーん．たとえ上記の例えが間違っていなかったとしても，
とても「わかりやすい」とは言えない．^^;

なひはやっぱり，駆動の違いのほうが．．．^^;

--
NaHi, nakahiro, a.k.a. NAKAMURA, Hiroshi
http://www.sarion.com  Sarion Systems Research