質問: 詳説正規表現第三版149p、151pにて (NFAエンジン) > > "制御が正規表現内の要素から要素に移っていくので、私はこれを"正規表現主導型"と呼んでいる" > > > (DFAエンジン) > > "テキストから走査された一つ一つの文字がエンジンを制御しているので"テキスト主導型"<中略>と呼べるだろう" > > > と書いてあります。 つまり、正規表現主導型は、正規表現にかけたい文字列を正規表現に当てはめながら進めていくのに対して、 DFAエンジンは、正規表現を正規表現にかけたい文字列、つまりテキストに当てはめながら進めていくからそのような名前を著者はつけたのだと思うのですが この認識はあっておりますか。
回答: NFA は非決定性有限オートマトン、DFA は決定性有限オートマトンと訳されます。 入力を一つ与えた時、遷移先が一意に決定するのが DFA で、決まらないのが NFA です。 NFA は正規表現を逐語訳したもので、正規表現の要素の一つ一つが各オートマトンと一対一対応します。 DFA はそれを変形したもので、正規表現の要素とオートマトンは一対一対応していません。 ここまでが大前提です。 さて、NFA のオートマトンは正規表現と一対一対応していると説明しました。つまり、入力を処理しているオートマトンがすなわち正規表現の特定の要素を表します。 これをもって作者は正規表現主導型と呼んだのでしょう。この言葉はその作者の独自の言葉だろうと思います。 かわって DFA のオートマトンは正規表現と一対一対応していないので、処理中のオートマトンが正規表現の特定の要素であるとは必ずしも言えません。 これをもってテキスト主導型と呼んだのでしょう。 いずれにせよ、独自の用語が無用の混乱を呼ぶようであれば、その用語にこだわらずアルゴリズムの本質を理解するために別の作者の書いた物を読むことをお勧めします。 アルゴリズムを理解して初めて作者の独自の用語が理解できることはあるでしょう。 本来理解を助けるために型を分けられたのだと思いますが、今は逆にその言い回し自体が理解を邪魔しているように見えます。 正規表現とテキストのどっちが主であるか、それがどういう意味を持つのかということは、DFA と NFA の開発に果たす役割を理解してからでも遅くはないと思います。