DFAでバックリファレンスというのは従来の設計では無理っぽい

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-dev/10657

私の記憶が正しければGNU grepは、使える場合にはDFAを使うこと
で高速化していたと思います。

たとえば、egrepでもDFA型で対応できないバックリファレンスを含
むものは、NFA型を使うことになるので同じような状況で、同じよ
うな理由で失敗します。