哪个正则表达式需要回溯? [英] Which regular expression requires backtracking?

问题描述

有三种实现正则表达式匹配的解决方案:DFA，NFA和回溯.我正在寻找示例:

There are three different solutions to implement regular expression matching: DFA, NFA and Backtracking. I am looking for examples:

• 一个正则表达式，可以使用DFA以及它为何足够使用DFA来解决.
• 一个正则表达式，它需要NFA以及需要NFA的原因.
• 一个正则表达式，它需要回溯以及必须进行回溯的原因.

对于一些有关该主题的优秀文献的建议也将很不错.

A recommendation for some good literature about this topic would be nice, too.

推荐答案

到目前为止，我发现的是:

What I found out so far is:

• 可以使用NFA实施的每个正则表达式，也可以使用DFA实施.每个NFA都可以转换为DFA.

• Every regular expression, which can be implemented with a NFA, can also be implemented with a DFA. Every NFA can be transformed into a DFA.

需要回溯的正则表达式是正则表达式，包含诸如/(a)\1/的反向引用.

Regular expressions, which require backtracking, are regular expressions, which contain back references like /(a)\1/.

这篇关于哪个正则表达式需要回溯?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！