我有一点形式语言的背景，最近我发现Java和其他语言使用所谓的扩展规则语言。由于我的背景，我一直认为在Java等语言中，当我调用compile for Pattern时，它会在后台生成DFA或Transducer。因此，我一直认为，无论我的正则表达式有多难看，无论正则表达式有多长时间，Pattern.matches或类似的方法都会在线性时间内运行。但这种假设似乎是不正确的。
我读到的一篇帖子似乎表明，一些Regex表达式确实在线性时间内运行，但我并不完全相信或信任一个人。
我最终会编写自己的Java正式正则表达式库（我发现现有的库只有GNU GPL许可证），但同时我对Java/C#regexs的时间复杂性有一些问题。希望确保我在其他地方读到的内容是正确的。
问题：
- 像\sRT\s这样的正式语言，Java/C#中正则表达式的匹配方法会解决线性或非线性时间中的成员关系吗
- 一般来说，我怎么知道给定正则语言的表达式成员资格问题是否是Regex的线性时间
我做文本分析，发现Java正则表达式不是DFA的正则表达式真的很沮丧。
由于我的背景，我一直认为在Java等语言中，当我调用compile for Pattern时，它会在后台生成DFA或Transducer。
这种观点在学术界很普遍。在实践中，正则表达式编译不会生成DFA然后执行它。我在这方面只有少量的经验；20世纪90年代，我曾在微软实现JavaScript的过程中简要研究过正则表达式编译系统。我们选择将"正则"表达式编译成一种简单的特定于域的字节码语言，然后为该语言构建一个解释器。
正如您所注意到的，这可能会导致重复回溯在输入长度上具有指数级的不良时间行为，但编译状态的构造在表达式大小上基本上是线性的。
所以，让我用另外两个问题来反驳你的问题——我注意到这些都是真实的问题，而不是修辞性的问题。
1） 每个实际上正则表达式都对应于一个具有n个状态的NDFA。相应的DFA可能需要多达2n态的叠加。那么，是什么阻止了在病理病例中构建DFA所需的时间呈指数级增长呢？运行时在输入中可能是线性的，但如果运行时在模式大小中是指数型的，那么基本上你只是在用一种非线性换另一种非线性。
2） 现在所谓的"正则"表达式根本不是那种；他们可以进行括号匹配。它们对应于下推自动机，而不是不确定性有限自动机。有没有一种线性算法可以为"正则"表达式构造相应的下推自动机？
正则表达式在许多语言中被实现为NFA，以支持回溯（请参阅http://msdn.microsoft.com/en-us/library/e347654k（v=vs.110）.aspx）。由于回溯，您可以构造在某些字符串上性能较差的正则表达式（请参阅http://www.regular-expressions.info/catastrophic.html)
至于分析正则表达式以确定它们的性能，我怀疑是否有一个很好的方法。您可以查找警告标志，如第二个链接示例中的复合回溯，但在某些情况下，即使这样也很难正确检测到。
Java对正则表达式的实现使用了NFA方法。这里有一个链接可以清楚地解释它。
基本上，一个写得不好但仍然正确的正则表达式可能会导致引擎性能不佳。例如，给定表达式(a+a+)+b和字符串aaaaaaaaaaaaaaa。可能需要一段时间（根据您的机器，从几秒钟到几分钟）才能发现没有对手。
NFA的最坏情况性能是几乎匹配的情况（给定示例）。因为表达式强制引擎探索每条路径（通过大量回溯）来确定不匹配。