regex - 可以将包含有序交替的正则表达式重写为仅使用无序交替吗？

Question

假设我有一个正则表达式语言支持文字、正负字符类、有序交替、贪婪量词 ? , * , 和 + ，以及非贪婪量词 ?? , *? , 和 +? . (这本质上是 PCRE 的一个子集，没有反向引用、环视断言或其他一些更高级的位。)用无序交替替换有序交替会降低这种形式主义的表达能力吗？

(无序交替——有时也称为“无序选择”——满足 L(S|T) = L(S) + L(T)，而有序交替满足 L(S|T) = L (S) + (L(T) - { a in L(T) : a extends some b in L(S) }). 具体来说，模式 a|aa 将匹配字符串 a 和 aa 如果交替是无序的，但只有 a 如果交替是有序的。)

换句话说，给定一个包含有序交替的模式 S，是否可以将该模式重写为不包含有序交替(但可能是无序交替)的等效模式 T？

如果在文献中考虑过这个问题，我会很感激任何人都可以提供的任何引用资料。关于扩展正则表达式形式主义的表达能力，我几乎没有提出任何理论工作(除了关于反向引用如何将您从常规语言转移到上下文无关语法的常见事情之外)。

Answer 1

在 http://swtch.com/~rsc/regexp/regexp3.html [“正则表达式是否匹配字符串的子字符串？如果匹配，在哪里？”] 有必要在“DFA”中引入优先级的概念(我怀疑你需要阅读整个系列才能理解，但是“DFA”是从 NFA 图“动态”扩展而来的，以处理有序的交替。虽然这只是对权威的呼吁，而不是证明，但我认为可以公平地说，如果 russ cox 不能做到(将有序交替表示为纯粹的 DFA)，那么没有人知道该怎么做。