我有一些正式语言的背景,最近我发现Java和其他语言使用的是扩展常规语言.由于我的背景,当我调用编译模式时,我总是假设使用Java之类的语言,它在后台生成了DFA或传感器.结果,无论我的正则表达式有多丑,无论我的正则表达式,Pattern.matches或类似方法在线性时间内运行多长时间,我总是假设.但这种假设似乎是不正确的.
我读过的帖子似乎暗示一些正则表达式确实在线性时间运行,但我并不完全相信或信任一个人.
我最终会编写自己的Java Formal Regular Expression库(我发现现有的只有GNU GPL许可证),但与此同时我对Java/C#regexs的时间复杂性有几个疑问.想要确保我在别处读到的内容是正确的.
问题:
像\ s RT\s这样的形式语言.,Java/C#中正则表达式的匹配方法是否会在线性或非线性时间内解析成员资格?
一般来说,我怎么知道给定的常规语言的表达式成员问题是否是正则表达式的线性时间?
我做文本分析,找出Java正则表达不是DFA真的是一个下降.