[Tokyo.pm] mastering regex

NAKAMURA, Hiroshi nakahiro @ sarion.co.jp
1999年 12月 14日 (火) 22:16:02 CST


なひです.

> 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



Tokyo-pm メーリングリストの案内