あまり取り上げられていないのでメモ。
例えば文字列「kumono-mukou」にパターン「kumono-(muko)?(mukou)?」をぶつけてみる。eregは「kumono-mukou」を返し、preg（_match）は「kumono-muko」を返す。
POSIXなeregは「最左最長」を求めるので、例え貪欲な量指定子（基本的には「有り」「出来るだけ多く」として進めていく）をもつ「(muko)?」を通過して、「kumono-muko」までは決定しても（残ってるのは最後の「u」だけだ）、「『(muko)?』は『?』なんだから、『無し』の場合もあるんだよな。試してみた方が良いかも」と律儀に確かめてくれる。
pregは従来型NFAなのでそこまではしない。最後に残った「u」に「(mukou)?」はマッチしない、と判断してそこで終了だ。「kumono-(muko)??(mukou)?」と無欲な量指定子を使えば「とりあえず、(muko)?はスキップして(mukou)?を試してみよう」となるので、「kumono-mukou」までマッチすることも出来る。ちなみに、eregでは「??」は使えない。無欲な量指定子はPOSIXとは相反するからだ。
eregは律儀に全てのパターンを調べようとするので、曖昧なパターンを与えるとかなり時間がかかってしまう。pregは1つマッチ結果を見つければそこで満足するので、マッチする内容が有れば速い（もっとも、どうやってもマッチしない場合はeregと同じぐらいバックトラックすることになるが）。曖昧なパターンとは組み合わせが多いパターンだ。量指定子の組み合わせによっては平気で「溝」の桁までバックトラックの数が増えるので、eregを使う際は注意が必要だ。
関係ないが、「非決定性有限オートマトン」という響きが格好いい。「強行偵察型非決定性有限オートマトン」とか、そんな感じがする。
http://yudai.arielworks.com/memo/2004/09/17/033015.trackback
末尾に「5 + 1」の計算結果を繋げて下さい。例えば計算結果が「17」の場合、「033015.trackback17」です。これは機械的なトラックバックスパムを防止するための措置です。