包含有序交替的正则表达式可以被重写为只使用无序交替吗？

Question

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

(无序交替-有时也称为“无序选择”-是这样的: L(S|T) = L(S) + L(T)，而有序交替是这样的: L(S|T) = L(S) + (L(T) -{a in L(T)：a在L(S) }中扩展了一些b)。具体地说，如果交替是无序的，则模式a|aa将匹配字符串a和aa，但如果交替是有序的，则仅匹配a。)

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

如果这个问题已经在文献中被考虑过，我将感谢任何人能提供的参考资料。我几乎没有发现任何关于扩展正则表达式形式的表达能力的理论工作(除了关于反向引用如何将您从常规语言转移到上下文无关语法的常见内容之外)。

Answer 1

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

Answer 2

我没有查阅任何文献，但我认为你可以为有序交替构造一个DFA，从而证明它不会以以下方式增加任何表达能力：

假设我们有正则表达式x||y，其中x和y是正则表达式，||<>e29>表示无序交替。如果是这样的话，我们可以构造DFA的接受x和y。我们将标记这些路径，DFA_y

• We将通过连接DFA_y

• For 和DFA_y

• For来分阶段为x||y构建DFA，方法是连接DFA_x和DFA_x中与某个字符串对应的每个路径a231(这里的路径我指的是图意义上没有遍历和边两次的路径，因此e132a是DFA_"a*"，但e136aa不是)...对于字母表的
• 中的每个符号，如果DFA_y将作为使用(即，如果在上运行，则E148DFA_y E249不会提前停止，但它不一定接受)和E150 DFA_x E251不接受，并且E253不接受E154的任何前缀作为E255创建从状态E156到E160的转换。在使用as

之后结束

​

​

1. 最终DFA的接受状态是两个输入DFA的所有接受状态，起始状态是DFA的起始状态

直观地说，它的作用是在输出DFA中创建两个区域。其中一个对应于交替的第一个参数，另一个对应于第二个参数。只要交替的第一个参数匹配，我们就留在第一部分。当遇到确定第一个参数不匹配的符号时，如果可能，此时我们切换到第二部分。如果这种方法是错误的，请发表评论。