3

正規表現マッチングを実装するには、DFA、NFA、およびバックトラッキングの 3 つの異なるソリューションがあります。私は例を探しています:

  • DFA で解決できる正規表現と、DFA で十分である理由。
  • NFA を必要とする正規表現と、NFA が必要な理由。
  • バックトラッキングが必要な正規表現と、バックトラッキングが必要な理由。

このトピックに関するいくつかの優れた文献の推奨もいいでしょう.

4

2 に答える 2

4

バックトラッキングという言葉には複数の意味があると思います-'.*a'文字列に一致するためにバックトラックする必要さえあります"lalaiiiiiii" （ .* 最初に文字列全体に一致するため-次に a 何にも一致しないため-その後、一度に1文字ずつ放棄されます、したがって、最終的な一致は "lala")

http://www.regular-expressions.info/を強くお勧めします

于 2012-02-16T00:44:26.020 に答える
-3

これまでにわかったことは次のとおりです。

  • NFA で実装できるすべての正規表現は、DFA でも実装できます。すべての NFA は DFA に変換できます。

  • バックトラッキングが必要な正規表現は、 のような後方参照を含む正規表現/(a)\1/です。

于 2011-12-13T16:31:32.640 に答える