>>280
自己レス。AI に聞いたら

| GNU grepでは、DFA の生成に On-the-Fly（実行時逐次的）な手法を採用していますが、
| それは基本的に部分集合構成法を逐次的に行うことを意味します。
| ε遷移の除去も、このプロセスの中で実質的に On-the-Fly で行われます。

とのことでした。やっぱε-除去も On-the-Fly なのか、ムズいなー

>>281
GNU grep の On-the-Fly 法は、到達しない状態ノードを作らないようにすることで
省メモリ化と高速化が目的なので、DFA の構造自体が動的に変わるものではないと思ってました。

で、言われるように後方参照は正規言語のクラスを超えてるので、DFA 型エンジンでは
普通は実現出来ないのだけど、「正規表現技術入門」では

| GNU grep は基本的に DFA 型ですが、部分的（後方参照への対応のためなど）に一部
| VM 型のアプローチもとっています。

とかさらっと書いてあるだけで、具体的な記述はないんすよね (やっぱ入門書だな)。

でも言われてみれば、On-the-Fly 的に動的に DFA を構成して行けば、それで後方参照も
実現出来そうな気がしてきた。バックトラックとか面倒そうだけど一考の価値はあるかも

GNU grep もそうやって実装してる ? かどうかは分からないけど