従来型のNFAだと、選択肢のマッチは貪欲ではなかったらしい。完全に勘違いしていた。
従来型のNFAは選択肢があると、左から順に検査して、1度通過した時点で満足してしまう。後続に迫られない限りは、それ以上のバックトラックはしない。例えば、文字列「foo」に「f(o|oo)」をマッチさせようとすると「fo」がマッチした時点で終了する。
PHPのpreg関数は少なくとも見かけ上は従来型のNFAらしく（Perl互換だし）、実際に試してみると、上記と同じ結果になった。
逆に、ereg関数はPOSIX拡張なので、最長一致が保証されている。実験してみると、「fo」には満足せずにバックトラックを続け、「foo」にマッチした（バックトラックが増えるのでその分遅くなる）。
同じ正規表現でもかなり差があるので互換性に注意する必要がある。もっとも、個人的にはeregを使うことはまず無いので、あまり関係ないが。